Module: sage.rings.integer_mod
Elements of
An element of the integers modulo
.
There are three types of integer_mod classes, depending on the size of the modulus.
int_fast32_t
(typically an int
);
this is used if the modulus is less than
int_fast64_t
(typically a long long
); this is used if the modulus is less than
mpz_t
; this can be used for an
arbitrarily large modulus.
All extend IntegerMod_abstract.
For efficency reasons, it stores the modulus (in all three forms, if possible) in a common (cdef) class NativeIntStruct rather than in the parent.
Author Log:
TESTS:
sage: R = Integers(101^3) sage: a = R(824362); b = R(205942) sage: a * b 851127
Module-level Functions
) |
Create an integer modulo
with the given parent.
This is mainly for internal use.
) |
Return the equivalence class of
modulo
as an element of
.
sage: x = Mod(12345678, 32098203845329048) sage: x 12345678 sage: x^100 1017322209155072
You can also use the lowercase version:
sage: mod(12,5) 2
) |
Return
where
is the Lucas function
defined by the recursive relation
with
.
REFERENCES: H. Postl. `Fast evaluation of Dickson Polynomials' Contrib. to General Algebra, Vol. 6 (1988) pp. 223-225
Author: Robert Bradshaw
TESTS:
sage: from sage.rings.integer_mod import fast_lucas, slow_lucas sage: all([fast_lucas(k, a) == slow_lucas(k, a) ... for a in Integers(23) ... for k in range(13)]) True
) |
Return True
if and only if x is an integer modulo
.
sage: is_IntegerMod(5) False sage: is_IntegerMod(Mod(5,10)) True
) |
Function to convert a Sage Integer into class NativeIntStruct.
NOTE: This function seems completely redundant, and is not used anywhere.
) |
Return the equivalence class of
modulo
as an element of
.
sage: x = Mod(12345678, 32098203845329048) sage: x 12345678 sage: x^100 1017322209155072
You can also use the lowercase version:
sage: mod(12,5) 2
) |
Lucas function defined using the standard definition, for consistency testing.
) |
Calculates the square root of
, where
is an integer mod
;
if
is not a perfect square, this returns an (incorrect) answer
without checking.
ALGORITHM:
Several cases based on residue class of
.
REFERENCES: Siguna Müller. `On the Computation of Square Roots in Finite Fields' Designs, Codes and Cryptography, Volume 31, Issue 3 (March 2004)
A. Oliver L. Atkin. `Probabilistic primality testing' (Section 4) In P. Flajolet and P. Zimmermann, editors, Analysis of Algorithms Seminar I. INRIA Research Report XXX, 1992. Summary by F. Morain. http://citeseer.ist.psu.edu/atkin92probabilistic.html
H. Postl. `Fast evaluation of Dickson Polynomials' Contrib. to General Algebra, Vol. 6 (1988) pp. 223-225
Author: Robert Bradshaw
TESTS: Every case appears in the first hundred primes.
sage: from sage.rings.integer_mod import square_root_mod_prime # sqrt() uses brute force for small p sage: all([square_root_mod_prime(a*a)^2 == a*a ... for p in prime_range(100) ... for a in Integers(p)]) True
) |
Calculates the square root of
, where
is an integer mod
.
ALGORITHM:
Perform
-adically by stripping off even powers of
to get
a unit and lifting
via Newton's method.
Author: Robert Bradshaw
sage: from sage.rings.integer_mod import square_root_mod_prime_power sage: a=Mod(17,2^20) sage: b=square_root_mod_prime_power(a,2,20) sage: b^2 == a True
sage: a=Mod(72,97^10) sage: b=square_root_mod_prime_power(a,97,10) sage: b^2 == a True
Class: Int_to_IntegerMod
sage: from sage.rings.integer_mod import Int_to_IntegerMod sage: Rs = [Integers(2**k) for k in range(1,50,10)] sage: [type(R(0)) for R in Rs] [<type 'sage.rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.integer_mod.IntegerMod_gmp'>, <type 'sage.rings.integer_mod.IntegerMod_gmp'>] sage: fs = [Int_to_IntegerMod(R) for R in Rs] sage: [f(-1) for f in fs] [1, 2047, 2097151, 2147483647, 2199023255551]
Special Functions: __init__,
_repr_type
) |
Class: Integer_to_IntegerMod
We make sure it works for every type.
sage: from sage.rings.integer_mod import Integer_to_IntegerMod sage: Rs = [Integers(10), Integers(10^5), Integers(10^10)] sage: [type(R(0)) for R in Rs] [<type 'sage.rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.integer_mod.IntegerMod_gmp'>] sage: fs = [Integer_to_IntegerMod(R) for R in Rs] sage: [f(-1) for f in fs] [9, 99999, 9999999999]
Special Functions: __init__,
_repr_type
) |
Class: IntegerMod_abstract
Functions: additive_order,
charpoly,
crt,
is_nilpotent,
is_one,
is_square,
is_unit,
log,
modulus,
multiplicative_order,
norm,
nth_root,
pari,
polynomial,
rational_reconstruction,
sqrt,
square_root,
trace
) |
Returns the additive order of self.
This is the same as self.order()
.
sage: Integers(20)(2).additive_order() 10 sage: Integers(20)(7).additive_order() 20 sage: Integers(90308402384902)(2).additive_order() 45154201192451
) |
Returns the characteristic polynomial of this element.
sage: k = GF(3) sage: a = k.gen() sage: a.charpoly('x') x + 2 sage: a + 2 0
Author: Craig Citro
) |
Use the Chinese Remainder Theorem to find an element of the
integers modulo the product of the moduli that reduces to self
and to other. The modulus of other must be coprime to the
modulus of self
.
sage: a = mod(3,5) sage: b = mod(2,7) sage: a.crt(b) 23
sage: a = mod(37,10^8) sage: b = mod(9,3^8) sage: a.crt(b) 125900000037
sage: b = mod(0,1) sage: a.crt(b) == a True sage: a.crt(b).modulus() 100000000
Author: Robert Bradshaw
) |
Return True
if self
is nilpotent, i.e., some power of self
is zero.
sage: a = Integers(90384098234^3) sage: factor(a.order()) 2^3 * 191^3 * 236607587^3 sage: b = a(2*191) sage: b.is_nilpotent() False sage: b = a(2*191*236607587) sage: b.is_nilpotent() True
ALGORITHM: Let
, where
is the modulus.
Then
is nilpotent if and only if
.
PROOF: This is clear if you reduce to the prime power case, which you can do via the Chinese Remainder Theorem.
We could alternatively factor
and check to see if the prime
divisors of
all divide
. This is asymptotically slower :-).
) |
sage: Mod(3,17).is_square() False sage: Mod(9,17).is_square() True sage: Mod(9,17*19^2).is_square() True sage: Mod(-1,17^30).is_square() True sage: Mod(1/9, next_prime(2^40)).is_square() True sage: Mod(1/25, next_prime(2^90)).is_square() True
TESTS:
sage: Mod(1/25, 2^8).is_square() True sage: Mod(1/25, 2^40).is_square() True
ALGORITHM:
Calculate the Jacobi symbol
at each prime
dividing
.
It must be 1 or 0 for each prime, and if it is 0 mod
,
where
, then
must be even or greater than
.
The case
is handled separately.
Author: Robert Bradshaw
) |
Return an integer
such that
, where
is
self
.
Input:
R.multiplicative_generator()
is used,
where R
is the parent of self
.
NOTE: The base must not be too big or the current implementation, which is in PARI, will fail.
sage: r = Integers(125) sage: b = r.multiplicative_generator()^3 sage: a = b^17 sage: a.log(b) 17 sage: a.log() 63
A bigger example.
sage: FF = FiniteField(2^32+61) sage: c = FF(4294967356) sage: x = FF(2) sage: a = c.log(x) sage: a 2147483678 sage: x^a 4294967356
Things that can go wrong. E.g., if the base is not a
generator for the multiplicative group, or not even a unit.
You can also use the generic function discrete_log
.
sage: a = Mod(9, 100); b = Mod(3,100) sage: a.log(b) Traceback (most recent call last): ... ValueError: base (=3) for discrete log must generate multiplicative group sage: sage.groups.generic.discrete_log(b^2,b) 2 sage: a = Mod(16, 100); b = Mod(4,100) sage: a.log(b) Traceback (most recent call last): ... ValueError: (8) PARI failed to compute discrete log (perhaps base is not a generator or is too large) sage: sage.groups.generic.discrete_log(a,b) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
Author Log:
) |
sage: Mod(3,17).modulus() 17
) |
Returns the multiplicative order of self.
sage: Mod(-1,5).multiplicative_order() 2 sage: Mod(1,5).multiplicative_order() 1 sage: Mod(0,5).multiplicative_order() Traceback (most recent call last): ... ArithmeticError: multiplicative order of 0 not defined since it is not a unit modulo 5
) |
Returns the norm of this element, which is itself. (This is here for compatibility with higher order finite fields.)
sage: k = GF(691) sage: a = k(389) sage: a.norm() 389
Author: Craig Citro
) |
Returns an
th root of
self
.
Input:
int
type)
False
); if True
, return all self
, instead of just one.
Author: David Roe (2007-10-3)
sage: k.<a> = GF(29) sage: b = a^2 + 5*a + 1 sage: b.nth_root(5) 24 sage: b.nth_root(7) Traceback (most recent call last): ... ValueError: no nth root sage: b.nth_root(4, all=True) [21, 20, 9, 8]
) |
Returns a constant polynomial representing this value.
sage: k = GF(7) sage: a = k.gen(); a 1 sage: a.polynomial() 1 sage: type(a.polynomial()) <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod _p'>
) |
sage: R = IntegerModRing(97) sage: a = R(2) / R(3) sage: a 33 sage: a.rational_reconstruction() 2/3
) |
Returns square root or square roots of self
modulo
.
Input:
True
); if True
, return a square
root in an extension ring, if necessary. Otherwise,
raise a ValueError if the square root is not
in the base ring.
False
); if True
, return all square
roots of self, instead of just one.
ALGORITHM: Calculates the square roots mod
for each of the
primes
dividing the order of the ring, then lifts them
-adically and uses the CRT to find a square root mod
.
See also square_root_mod_prime_power
and
square_root_mod_prime
(in this module) for more
algorithmic details.
sage: mod(-1, 17).sqrt() 4 sage: mod(5, 389).sqrt() 86 sage: mod(7, 18).sqrt() 5 sage: a = mod(14, 5^60).sqrt() sage: a*a 14 sage: mod(15, 389).sqrt(extend=False) Traceback (most recent call last): ... ValueError: self must be a square sage: Mod(1/9, next_prime(2^40)).sqrt()^(-2) 9 sage: Mod(1/25, next_prime(2^90)).sqrt()^(-2) 25
sage: a = Mod(3,5); a 3 sage: x = Mod(-1, 360) sage: x.sqrt(extend=False) Traceback (most recent call last): ... ValueError: self must be a square sage: y = x.sqrt(); y sqrt359 sage: y.parent() Univariate Quotient Polynomial Ring in sqrt359 over Ring of integers modulo 360 with modulus x^2 + 1 sage: y^2 359
We compute all square roots in several cases:
sage: R = Integers(5*2^3*3^2); R Ring of integers modulo 360 sage: R(40).sqrt(all=True) [20, 160, 200, 340] sage: [x for x in R if x^2 == 40] # Brute force verification [20, 160, 200, 340] sage: R(1).sqrt(all=True) [1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359] sage: R(0).sqrt(all=True) [0, 60, 120, 180, 240, 300]
sage: R = Integers(5*13^3*37); R Ring of integers modulo 406445 sage: v = R(-1).sqrt(all=True); v [78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592] sage: [x^2 for x in v] [406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444] sage: v = R(169).sqrt(all=True); min(v), -max(v), len(v) (13, 13, 104) sage: all([x^2==169 for x in v]) True
Modulo a power of 2:
sage: R = Integers(2^7); R Ring of integers modulo 128 sage: a = R(17) sage: a.sqrt() 23 sage: a.sqrt(all=True) [23, 41, 87, 105] sage: [x for x in R if x^2==17] [23, 41, 87, 105]
) |
Returns square root or square roots of self
modulo
.
Input:
True
); if True
, return a square
root in an extension ring, if necessary. Otherwise,
raise a ValueError if the square root is not
in the base ring.
False
); if True
, return all square
roots of self, instead of just one.
ALGORITHM: Calculates the square roots mod
for each of the
primes
dividing the order of the ring, then lifts them
-adically and uses the CRT to find a square root mod
.
See also square_root_mod_prime_power
and
square_root_mod_prime
(in this module) for more
algorithmic details.
sage: mod(-1, 17).sqrt() 4 sage: mod(5, 389).sqrt() 86 sage: mod(7, 18).sqrt() 5 sage: a = mod(14, 5^60).sqrt() sage: a*a 14 sage: mod(15, 389).sqrt(extend=False) Traceback (most recent call last): ... ValueError: self must be a square sage: Mod(1/9, next_prime(2^40)).sqrt()^(-2) 9 sage: Mod(1/25, next_prime(2^90)).sqrt()^(-2) 25
sage: a = Mod(3,5); a 3 sage: x = Mod(-1, 360) sage: x.sqrt(extend=False) Traceback (most recent call last): ... ValueError: self must be a square sage: y = x.sqrt(); y sqrt359 sage: y.parent() Univariate Quotient Polynomial Ring in sqrt359 over Ring of integers modulo 360 with modulus x^2 + 1 sage: y^2 359
We compute all square roots in several cases:
sage: R = Integers(5*2^3*3^2); R Ring of integers modulo 360 sage: R(40).sqrt(all=True) [20, 160, 200, 340] sage: [x for x in R if x^2 == 40] # Brute force verification [20, 160, 200, 340] sage: R(1).sqrt(all=True) [1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359] sage: R(0).sqrt(all=True) [0, 60, 120, 180, 240, 300]
sage: R = Integers(5*13^3*37); R Ring of integers modulo 406445 sage: v = R(-1).sqrt(all=True); v [78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592] sage: [x^2 for x in v] [406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444] sage: v = R(169).sqrt(all=True); min(v), -max(v), len(v) (13, 13, 104) sage: all([x^2==169 for x in v]) True
Modulo a power of 2:
sage: R = Integers(2^7); R Ring of integers modulo 128 sage: a = R(17) sage: a.sqrt() 23 sage: a.sqrt(all=True) [23, 41, 87, 105] sage: [x for x in R if x^2==17] [23, 41, 87, 105]
) |
Returns the trace of this element, which is itself. (This is here for compatibility with higher order finite fields.)
sage: k = GF(691) sage: a = k(389) sage: a.trace() 389
Author: Craig Citro
Special Functions: __abs__,
__init__,
__reduce__,
_balanced_abs,
_gap_init_,
_integer_,
_latex_,
_magma_init_,
_pari_init_,
_rational_,
_repr_
) |
Raise an error message, since abs(x)
makes no sense when x
is an
integer modulo
.
sage: abs(Mod(2,3)) Traceback (most recent call last): ... ArithmeticError: absolute valued not defined on integers modulo n.
) |
sage: a = Mod(4,5); a 4 sage: loads(a.dumps()) == a True sage: a = Mod(-1,5^30)^25; sage: loads(a.dumps()) == a True
) |
This function returns
or
, whichever has a positive
representative in
.
This is used so that the same square root is always returned, despite the possibly probabalistic nature of the underlying algorithm.
) |
Return string representation of corresponding GAP object.
This can be slow since non-prime GAP finite field elements are represented as powers of a generator for the multiplicative group, so the discrete log problem must be solved.
Note:
This function will create a meaningless GAP object if the
modulus is not a power of a prime. Also, the modulus must
be
.
sage: a = Mod(2,19) sage: gap(a) Z(19) sage: a._gap_(gap) Z(19) sage: gap(a).Int() 2 sage: b = Mod(0,25) sage: gap(b) 0*Z(5)
) |
) |
) |
Coercion to Magma.
sage: a = Integers(15)(4) sage: b = magma(a) # optional sage: b.Type() # optional RngIntResElt sage: b^2 # optional 1
) |
) |
) |
Class: IntegerMod_gmp
Author: Robert Bradshaw (2006-08-24)
Functions: is_one,
is_unit,
lift
) |
Returns True
if this is
, otherwise
False
.
sage: mod(1,5^23).is_one() True sage: mod(0,5^23).is_one() False
) |
Return True iff this element is a unit.
sage: mod(13, 5^23).is_unit() True sage: mod(25, 5^23).is_unit() False
) |
Lift an integer modulo
to the integers.
sage: a = Mod(8943, 2^70); type(a) <type 'sage.rings.integer_mod.IntegerMod_gmp'> sage: lift(a) 8943 sage: a.lift() 8943
Special Functions: __copy__,
__crt,
__eq__,
__float__,
__ge__,
__gt__,
__index__,
__init__,
__int__,
__invert__,
__le__,
__long__,
__lshift__,
__lt__,
__mod__,
__ne__,
__pow__,
__rlshift__,
__rmod__,
__rpow__,
__rrshift__,
__rshift__
) |
) |
) |
) |
Needed so integers modulo
can be used as list indices.
sage: v = [1,2,3,4,5] sage: v[Mod(3,10^20)] 4
) |
) |
Return the multiplicative inverse of self.
sage: a = mod(3,10^100); type(a) <type 'sage.rings.integer_mod.IntegerMod_gmp'> sage: ~a 666666666666666666666666666666666666666666666666666666666666666666666666666 6666666666666666666666667 sage: ~mod(2,10^100) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
) |
) |
Multiply self by
right
quickly via bit shifting
and modulus.
sage: e = Mod(19, 10^10) sage: e << 102 9443608576
) |
) |
Return self
shifted right by right bits. (In
,
this is nothing like division.)
sage: e = Mod(1000001, 2^32-1) sage: e >> 5 31250 sage: a = Mod(3, 5) sage: a >> 1 1 sage: a / 2 4
Class: IntegerMod_hom
Special Functions: __init__
Class: IntegerMod_int
Author: Robert Bradshaw (2006-08-24)
Functions: is_one,
is_unit,
lift,
sqrt
) |
Returns True
if this is
, otherwise
False
.
sage: mod(6,5).is_one() True sage: mod(0,5).is_one() False
) |
Return True iff this element is a unit
sage: a=Mod(23,100) sage: a.is_unit() True sage: a=Mod(24,100) sage: a.is_unit() False
) |
Lift an integer modulo
to the integers.
sage: a = Mod(8943, 2^10); type(a) <type 'sage.rings.integer_mod.IntegerMod_int'> sage: lift(a) 751 sage: a.lift() 751
) |
Returns square root or square roots of self
modulo
.
Input:
True
); if True
, return a square
root in an extension ring, if necessary. Otherwise,
raise a ValueError if the square root is not
in the base ring.
False
); if True
, return all square
roots of self, instead of just one.
ALGORITHM: Calculates the square roots mod
for each of the
primes
dividing the order of the ring, then lifts them
-adically and uses the CRT to find a square root mod
.
See also square_root_mod_prime_power
and
square_root_mod_prime
(in this module) for more
algorithmic details.
sage: mod(-1, 17).sqrt() 4 sage: mod(5, 389).sqrt() 86 sage: mod(7, 18).sqrt() 5 sage: a = mod(14, 5^60).sqrt() sage: a*a 14 sage: mod(15, 389).sqrt(extend=False) Traceback (most recent call last): ... ValueError: self must be a square sage: Mod(1/9, next_prime(2^40)).sqrt()^(-2) 9 sage: Mod(1/25, next_prime(2^90)).sqrt()^(-2) 25
sage: a = Mod(3,5); a 3 sage: x = Mod(-1, 360) sage: x.sqrt(extend=False) Traceback (most recent call last): ... ValueError: self must be a square sage: y = x.sqrt(); y sqrt359 sage: y.parent() Univariate Quotient Polynomial Ring in sqrt359 over Ring of integers modulo 360 with modulus x^2 + 1 sage: y^2 359
We compute all square roots in several cases:
sage: R = Integers(5*2^3*3^2); R Ring of integers modulo 360 sage: R(40).sqrt(all=True) [20, 160, 200, 340] sage: [x for x in R if x^2 == 40] # Brute force verification [20, 160, 200, 340] sage: R(1).sqrt(all=True) [1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359] sage: R(0).sqrt(all=True) [0, 60, 120, 180, 240, 300]
sage: R = Integers(5*13^3*37); R Ring of integers modulo 406445 sage: v = R(-1).sqrt(all=True); v [78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592] sage: [x^2 for x in v] [406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444] sage: v = R(169).sqrt(all=True); min(v), -max(v), len(v) (13, 13, 104) sage: all([x^2==169 for x in v]) True
Modulo a power of 2:
sage: R = Integers(2^7); R Ring of integers modulo 128 sage: a = R(17) sage: a.sqrt() 23 sage: a.sqrt(all=True) [23, 41, 87, 105] sage: [x for x in R if x^2==17] [23, 41, 87, 105]
Special Functions: __copy__,
__crt,
__eq__,
__float__,
__ge__,
__gt__,
__index__,
__init__,
__int__,
__invert__,
__le__,
__long__,
__lshift__,
__lt__,
__mod__,
__ne__,
__pow__,
__rlshift__,
__rmod__,
__rpow__,
__rrshift__,
__rshift__,
_balanced_abs,
_make_new_with_parent_c
) |
) |
Use the Chinese Remainder Theorem to find an element of the integers modulo the product of the moduli that reduces to self and to other. The modulus of other must be coprime to the modulus of self.
sage: a = mod(3,5) sage: b = mod(2,7) sage: a.crt(b) 23
Author: Robert Bradshaw
) |
) |
Needed so integers modulo
can be used as list indices.
sage: v = [1,2,3,4,5] sage: v[Mod(10,7)] 4
) |
) |
Return the multiplicative inverse of self.
sage: ~mod(7,100) 43
) |
) |
Multiply self by
right
very quickly via bit shifting.
sage: e = Mod(5, 2^10 - 1) sage: e<<5 160 sage: e*2^5 160
) |
) |
Divide self by
and take floor via bit shifting.
sage: e = Mod(8, 2^5 - 1) sage: e >> 3 1 sage: int(e)/int(2^3) 1
) |
This function returns
or
, whichever has a positive
representative in
.
) |
Class: IntegerMod_int64
Author: Robert Bradshaw (2006-09-14)
Functions: is_one,
is_unit,
lift
) |
Returns True
if this is
, otherwise
False
.
sage: (mod(-1,5^10)^2).is_one() True sage: mod(0,5^10).is_one() False
) |
Return True iff this element is a unit.
sage: mod(13, 5^10).is_unit() True sage: mod(25, 5^10).is_unit() False
) |
Lift an integer modulo
to the integers.
sage: a = Mod(8943, 2^25); type(a) <type 'sage.rings.integer_mod.IntegerMod_int64'> sage: lift(a) 8943 sage: a.lift() 8943
Special Functions: __copy__,
__crt,
__eq__,
__float__,
__ge__,
__gt__,
__index__,
__init__,
__int__,
__invert__,
__le__,
__long__,
__lshift__,
__lt__,
__mod__,
__ne__,
__pow__,
__rlshift__,
__rmod__,
__rpow__,
__rrshift__,
__rshift__,
_balanced_abs
) |
) |
Use the Chinese Remainder Theorem to find an element of the integers modulo the product of the moduli that reduces to self and to other. The modulus of other must be coprime to the modulus of self.
sage: a = mod(3,5^10) sage: b = mod(2,7) sage: a.crt(b) 29296878 sage: type(a.crt(b)) == type(b.crt(a)) and type(a.crt(b)) == type(mod(1, 7 * 5^10)) True
sage: a = mod(3,10^10) sage: b = mod(2,9) sage: a.crt(b) 80000000003 sage: type(a.crt(b)) == type(b.crt(a)) and type(a.crt(b)) == type(mod(1, 9 * 10^10)) True
Author: Robert Bradshaw
) |
Coerce self to a float.
sage: a = Mod(8943, 2^35) sage: float(a) 8943.0
) |
Needed so integers modulo
can be used as list indices.
sage: v = [1,2,3,4,5] sage: v[Mod(3, 2^20)] 4
) |
) |
Return the multiplicative inverse of self.
sage: a = mod(7,2^40); type(a) <type 'sage.rings.integer_mod.IntegerMod_gmp'> sage: ~a 471219269047 sage: a 7
) |
) |
sage: e = Mod(5, 2^31 - 1) sage: e<<32 10 sage: e*2^32 10
) |
) |
Divide self by
and take floor via bit shifting.
sage: e = Mod(8, 2^31 - 1) sage: e >> 3 1 sage: int(e)/int(2^3) 1
) |
This function returns
or
, whichever has a positive
representative in
.
Class: IntegerMod_to_IntegerMod
sage: from sage.rings.integer_mod import IntegerMod_to_IntegerMod sage: Rs = [Integers(3**k) for k in range(1,30,5)] sage: [type(R(0)) for R in Rs] [<type 'sage.rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.integer_mod.IntegerMod_gmp'>, <type 'sage.rings.integer_mod.IntegerMod_gmp'>] sage: fs = [IntegerMod_to_IntegerMod(S, R) for R in Rs for S in Rs if S is not R and S.order() > R.order()] sage: all([f(-1) == f.codomain()(-1) for f in fs]) True sage: [f(-1) for f in fs] [2, 2, 2, 2, 2, 728, 728, 728, 728, 177146, 177146, 177146, 43046720, 43046720, 10460353202]
Special Functions: __init__,
_repr_type
) |
Class: NativeIntStruct
We may also store a cached table of all elements of a given ring in this class.
Functions: precompute_table
) |
Function to compute and cache all elements of this class.
If inverses==True, also computes and caches the inverses of the invertible elments
Special Functions: __init__,
__reduce__,
_get_table
) |
) |
See About this document... for information on suggesting changes.