Elements of \(\ZZ/n\ZZ\)#
An element of the integers modulo \(n\).
There are three types of integer_mod classes, depending on the size of the modulus.
IntegerMod_int
stores its value in aint_fast32_t
(typically anint
); this is used if the modulus is less than \(\sqrt{2^{31}-1}\).IntegerMod_int64
stores its value in aint_fast64_t
(typically along long
); this is used if the modulus is less than \(2^{31}-1\). In many places, we assume that the values and the modulus actually fit inside anunsigned long
.IntegerMod_gmp
stores its value in ampz_t
; this can be used for an arbitrarily large modulus.
All extend IntegerMod_abstract
.
For efficiency reasons, it stores the modulus (in all three forms,
if possible) in a common (cdef) class
NativeIntStruct
rather than in the parent.
AUTHORS:
Robert Bradshaw: most of the work
Didier Deshommes: bit shifting
William Stein: editing and polishing; new arith architecture
Robert Bradshaw: implement native is_square and square_root
William Stein: sqrt
Maarten Derickx: moved the valuation code from the global valuation function to here
- class sage.rings.finite_rings.integer_mod.Int_to_IntegerMod#
Bases:
IntegerMod_hom
EXAMPLES:
We make sure it works for every type.
sage: from sage.rings.finite_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] [<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>, <class 'sage.rings.finite_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]
- sage.rings.finite_rings.integer_mod.IntegerMod(parent, value)#
Create an integer modulo \(n\) with the given parent.
This is mainly for internal use.
EXAMPLES:
sage: from sage.rings.finite_rings.integer_mod import IntegerMod sage: R = IntegerModRing(100) sage: type(R._pyx_order.table) <class 'list'> sage: IntegerMod(R, 42) 42 sage: IntegerMod(R, 142) 42 sage: IntegerMod(R, 10^100 + 42) 42 sage: IntegerMod(R, -9158) 42
- class sage.rings.finite_rings.integer_mod.IntegerMod_abstract#
Bases:
FiniteRingElement
EXAMPLES:
sage: a = Mod(10, 30^10); a 10 sage: type(a) <class 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: loads(a.dumps()) == a True
- additive_order()#
Returns the additive order of self.
This is the same as
self.order()
.EXAMPLES:
sage: Integers(20)(2).additive_order() 10 sage: Integers(20)(7).additive_order() 20 sage: Integers(90308402384902)(2).additive_order() 45154201192451
- charpoly(var='x')#
Returns the characteristic polynomial of this element.
EXAMPLES:
sage: k = GF(3) sage: a = k.gen() sage: a.charpoly('x') x + 2 sage: a + 2 0
AUTHORS:
Craig Citro
- crt(other)#
Use the Chinese Remainder Theorem to find an element of the integers modulo the product of the moduli that reduces to
self
and toother
. The modulus ofother
must be coprime to the modulus ofself
.EXAMPLES:
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
AUTHORS:
Robert Bradshaw
- divides(other)#
Test wheter
self
dividesother
.EXAMPLES:
sage: R = Zmod(6) sage: R(2).divides(R(4)) True sage: R(4).divides(R(2)) True sage: R(2).divides(R(3)) False
- generalised_log()#
Return integers \([n_1, \ldots, n_d]\) such that
\[\prod_{i=1}^d x_i^{n_i} = \text{self},\]where \(x_1, \dots, x_d\) are the generators of the unit group returned by
self.parent().unit_gens()
.EXAMPLES:
sage: m = Mod(3, 1568) sage: v = m.generalised_log(); v [1, 3, 1] sage: prod([Zmod(1568).unit_gens()[i] ** v[i] for i in [0..2]]) 3
See also
The method
log()
.Warning
The output is given relative to the set of generators obtained by passing
algorithm='sage'
to the methodunit_gens()
of the parent (which is the default). Specifyingalgorithm='pari'
usually yields a different set of generators that is incompatible with this method.
- is_nilpotent()#
Return
True
ifself
is nilpotent, i.e., some power ofself
is zero.EXAMPLES:
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 \(m \geq \log_2(n)\), where \(n\) is the modulus. Then \(x \in \ZZ/n\ZZ\) is nilpotent if and only if \(x^m = 0\).
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 \(n\) and check to see if the prime divisors of \(n\) all divide \(x\). This is asymptotically slower :-).
- is_one()#
- is_primitive_root()#
Determines whether this element generates the group of units modulo n.
This is only possible if the group of units is cyclic, which occurs if n is 2, 4, a power of an odd prime or twice a power of an odd prime.
EXAMPLES:
sage: mod(1,2).is_primitive_root() True sage: mod(3,4).is_primitive_root() True sage: mod(2,7).is_primitive_root() False sage: mod(3,98).is_primitive_root() True sage: mod(11,1009^2).is_primitive_root() True
- is_square()#
EXAMPLES:
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
ALGORITHM: Calculate the Jacobi symbol \((\mathtt{self}/p)\) at each prime \(p\) dividing \(n\). It must be 1 or 0 for each prime, and if it is 0 mod \(p\), where \(p^k || n\), then \(ord_p(\mathtt{self})\) must be even or greater than \(k\).
The case \(p = 2\) is handled separately.
AUTHORS:
Robert Bradshaw
- is_unit()#
- lift_centered()#
Lift
self
to a centered congruent integer.OUTPUT:
The unique integer \(i\) such that \(-n/2 < i \leq n/2\) and \(i = self \mod n\) (where \(n\) denotes the modulus).
EXAMPLES:
sage: Mod(0,5).lift_centered() 0 sage: Mod(1,5).lift_centered() 1 sage: Mod(2,5).lift_centered() 2 sage: Mod(3,5).lift_centered() -2 sage: Mod(4,5).lift_centered() -1 sage: Mod(50,100).lift_centered() 50 sage: Mod(51,100).lift_centered() -49 sage: Mod(-1,3^100).lift_centered() -1
- log(b=None, logarithm_exists=None)#
Compute the discrete logarithm of this element to base \(b\), that is, return an integer \(x\) such that \(b^x = a\), where \(a\) is
self
.INPUT:
self
- unit modulo \(n\)b
- a unit modulo \(n\). Ifb
is not given,R.multiplicative_generator()
is used, whereR
is the parent ofself
.
OUTPUT: Integer \(x\) such that \(b^x = a\), if this exists; a ValueError otherwise.
Note
The algorithm first factors the modulus, then invokes Pari’s
znlog
function for each odd prime power in the factorization of the modulus. This method can be quite slow for large moduli.EXAMPLES:
sage: r = Integers(125) sage: b = r.multiplicative_generator()^3 sage: a = b^17 sage: a.log(b) 17 sage: a.log() 51
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
An example with a highly composite modulus:
sage: m = 2^99 * 77^7 * 123456789 * 13712923537615486607^2 sage: (Mod(5,m)^5735816763073854953388147237921).log(5) 5735816763073854953388147237921
Errors are generated if the logarithm doesn’t exist or the inputs are not units:
sage: Mod(3, 7).log(Mod(2, 7)) Traceback (most recent call last): ... ValueError: no logarithm of 3 found to base 2 modulo 7 sage: a = Mod(16, 100); b = Mod(4,100) sage: a.log(b) Traceback (most recent call last): ... ValueError: logarithm of 16 is not defined since it is not a unit modulo 100
AUTHORS:
David Joyner and William Stein (2005-11)
William Stein (2007-01-27): update to use PARI as requested by David Kohel.
Simon King (2010-07-07): fix a side effect on PARI
Lorenz Panny (2021): speedups for composite moduli
- minimal_polynomial(var='x')#
Returns the minimal polynomial of this element.
EXAMPLES:
sage: GF(241, 'a')(1).minimal_polynomial(var = 'z') z + 240
- minpoly(var='x')#
Returns the minimal polynomial of this element.
EXAMPLES:
sage: GF(241, 'a')(1).minpoly() x + 240
- modulus()#
EXAMPLES:
sage: Mod(3,17).modulus() 17
- multiplicative_order()#
Returns the multiplicative order of self.
EXAMPLES:
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
- norm()#
Returns the norm of this element, which is itself. (This is here for compatibility with higher order finite fields.)
EXAMPLES:
sage: k = GF(691) sage: a = k(389) sage: a.norm() 389
AUTHORS:
Craig Citro
- nth_root(n, extend=False, all=False, algorithm=None, cunningham=False)#
Returns an \(n\)th root of
self
.INPUT:
n
- integer \(\geq 1\)extend
- bool (default: True); if True, return an nth root in an extension ring, if necessary. Otherwise, raise a ValueError if the root is not in the base ring. Warning: this option is not implemented!all
- bool (default:False
); ifTrue
, return all \(n\)th roots ofself
, instead of just one.algorithm
- string (default: None); The algorithm for the prime modulus case. CRT and p-adic log techniques are used to reduce to this case. ‘Johnston’ is the only currently supported option.cunningham
- bool (default:False
); In some cases, factorization ofn
is computed. If cunningham is set toTrue
, the factorization ofn
is computed using trial division for all primes in the so called Cunningham table. Refer to sage.rings.factorint.factor_cunningham for more information. You need to install an optional package to use this method, this can be done with the following command linesage -i cunningham_tables
OUTPUT:
If self has an \(n\)th root, returns one (if
all
isFalse
) or a list of all of them (ifall
isTrue
). Otherwise, raises aValueError
(ifextend
isFalse
) or aNotImplementedError
(ifextend
isTrue
).Warning
The ‘extend’ option is not implemented (yet).
NOTE:
If \(n = 0\):
if
all=True
:if
self=1
: all nonzero elements of the parent are returned in a list. Note that this could be very expensive for large parents.otherwise: an empty list is returned
if
all=False
:if
self=1
:self
is returnedotherwise; a
ValueError
is raised
If \(n < 0\):
if self is invertible, the \((-n)\)th root of the inverse of self is returned
otherwise a
ValueError
is raised or empty list returned.
EXAMPLES:
sage: K = GF(31) sage: a = K(22) sage: K(22).nth_root(7) 13 sage: K(25).nth_root(5) 5 sage: K(23).nth_root(3) 29 sage: mod(225,2^5*3^2).nth_root(4, all=True) [225, 129, 33, 63, 255, 159, 9, 201, 105, 279, 183, 87, 81, 273, 177, 207, 111, 15, 153, 57, 249, 135, 39, 231] sage: mod(275,2^5*7^4).nth_root(7, all=True) [58235, 25307, 69211, 36283, 3355, 47259, 14331] sage: mod(1,8).nth_root(2,all=True) [1, 7, 5, 3] sage: mod(4,8).nth_root(2,all=True) [2, 6] sage: mod(1,16).nth_root(4,all=True) [1, 15, 13, 3, 9, 7, 5, 11] sage: (mod(22,31)^200).nth_root(200) 5 sage: mod(3,6).nth_root(0,all=True) [] sage: mod(3,6).nth_root(0) Traceback (most recent call last): ... ValueError sage: mod(1,6).nth_root(0,all=True) [1, 2, 3, 4, 5]
ALGORITHM:
The default for prime modulus is currently an algorithm described in [Joh1999].
AUTHORS:
David Roe (2010-02-13)
- polynomial(var='x')#
Returns a constant polynomial representing this value.
EXAMPLES:
sage: k = GF(7) sage: a = k.gen(); a 1 sage: a.polynomial() 1 sage: type(a.polynomial()) <class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
- rational_reconstruction()#
Use rational reconstruction to try to find a lift of this element to the rational numbers.
EXAMPLES:
sage: R = IntegerModRing(97) sage: a = R(2) / R(3) sage: a 33 sage: a.rational_reconstruction() 2/3
This method is also inherited by prime finite fields elements:
sage: k = GF(97) sage: a = k(RationalField()('2/3')) sage: a 33 sage: a.rational_reconstruction() 2/3
- sqrt(extend=True, all=False)#
Return square root or square roots of
self
modulo \(n\).INPUT:
extend
- bool (default:True
); ifTrue
, return a square root in an extension ring, if necessary. Otherwise, raise aValueError
if the square root is not in the base ring.all
- bool (default:False
); ifTrue
, return {all} square roots of self, instead of just one.
ALGORITHM: Calculates the square roots mod \(p\) for each of the primes \(p\) dividing the order of the ring, then lifts them \(p\)-adically and uses the CRT to find a square root mod \(n\).
See also
square_root_mod_prime_power()
andsquare_root_mod_prime()
for more algorithmic details.EXAMPLES:
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
sage: t = FiniteField(next_prime(2^100))(4) sage: t.sqrt(extend = False, all = True) [2, 1267650600228229401496703205651] sage: t = FiniteField(next_prime(2^100))(2) sage: t.sqrt(extend = False, all = 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]
- square_root(extend=True, all=False)#
Return square root or square roots of
self
modulo \(n\).INPUT:
extend
- bool (default:True
); ifTrue
, return a square root in an extension ring, if necessary. Otherwise, raise aValueError
if the square root is not in the base ring.all
- bool (default:False
); ifTrue
, return {all} square roots of self, instead of just one.
ALGORITHM: Calculates the square roots mod \(p\) for each of the primes \(p\) dividing the order of the ring, then lifts them \(p\)-adically and uses the CRT to find a square root mod \(n\).
See also
square_root_mod_prime_power()
andsquare_root_mod_prime()
for more algorithmic details.EXAMPLES:
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
sage: t = FiniteField(next_prime(2^100))(4) sage: t.sqrt(extend = False, all = True) [2, 1267650600228229401496703205651] sage: t = FiniteField(next_prime(2^100))(2) sage: t.sqrt(extend = False, all = 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]
- trace()#
Returns the trace of this element, which is itself. (This is here for compatibility with higher order finite fields.)
EXAMPLES:
sage: k = GF(691) sage: a = k(389) sage: a.trace() 389
AUTHORS:
Craig Citro
- valuation(p)#
The largest power r such that m is in the ideal generated by p^r or infinity if there is not a largest such power. However it is an error to take the valuation with respect to a unit.
Note
This is not a valuation in the mathematical sense. As shown with the examples below.
EXAMPLES:
This example shows that the (a*b).valuation(n) is not always the same as a.valuation(n) + b.valuation(n)
sage: R=ZZ.quo(9) sage: a=R(3) sage: b=R(6) sage: a.valuation(3) 1 sage: a.valuation(3) + b.valuation(3) 2 sage: (a*b).valuation(3) +Infinity
The valuation with respect to a unit is an error
sage: a.valuation(4) Traceback (most recent call last): ... ValueError: Valuation with respect to a unit is not defined.
- class sage.rings.finite_rings.integer_mod.IntegerMod_gmp#
Bases:
IntegerMod_abstract
Elements of \(\ZZ/n\ZZ\) for n not small enough to be operated on in word size.
AUTHORS:
Robert Bradshaw (2006-08-24)
- gcd(other)#
Greatest common divisor
Returns the “smallest” generator in \(\ZZ / N\ZZ\) of the ideal generated by
self
andother
.INPUT:
other
– an element of the same ring as this one.
EXAMPLES:
sage: mod(2^3*3^2*5, 3^3*2^2*17^8).gcd(mod(2^4*3*17, 3^3*2^2*17^8)) 12 sage: mod(0,17^8).gcd(mod(0,17^8)) 0
- is_one()#
Returns
True
if this is \(1\), otherwiseFalse
.EXAMPLES:
sage: mod(1,5^23).is_one() True sage: mod(0,5^23).is_one() False
- is_unit()#
Return True iff this element is a unit.
EXAMPLES:
sage: mod(13, 5^23).is_unit() True sage: mod(25, 5^23).is_unit() False
- lift()#
Lift an integer modulo \(n\) to the integers.
EXAMPLES:
sage: a = Mod(8943, 2^70); type(a) <class 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: lift(a) 8943 sage: a.lift() 8943
- class sage.rings.finite_rings.integer_mod.IntegerMod_int#
Bases:
IntegerMod_abstract
Elements of \(\ZZ/n\ZZ\) for n small enough to be operated on in 32 bits
AUTHORS:
Robert Bradshaw (2006-08-24)
EXAMPLES:
sage: a = Mod(10,30); a 10 sage: loads(a.dumps()) == a True
- gcd(other)#
Greatest common divisor
Returns the “smallest” generator in \(\ZZ / N\ZZ\) of the ideal generated by
self
andother
.INPUT:
other
– an element of the same ring as this one.
EXAMPLES:
sage: R = Zmod(60); S = Zmod(72) sage: a = R(40).gcd(S(30)); a 2 sage: a.parent() Ring of integers modulo 12 sage: b = R(17).gcd(60); b 1 sage: b.parent() Ring of integers modulo 60 sage: mod(72*5, 3^3*2^2*17^2).gcd(mod(48*17, 3^3*2^2*17^2)) 12 sage: mod(0,1).gcd(mod(0,1)) 0
- is_one()#
Returns
True
if this is \(1\), otherwiseFalse
.EXAMPLES:
sage: mod(6,5).is_one() True sage: mod(0,5).is_one() False sage: mod(1, 1).is_one() True sage: Zmod(1).one().is_one() True
- is_unit()#
Return True iff this element is a unit
EXAMPLES:
sage: a=Mod(23,100) sage: a.is_unit() True sage: a=Mod(24,100) sage: a.is_unit() False
- lift()#
Lift an integer modulo \(n\) to the integers.
EXAMPLES:
sage: a = Mod(8943, 2^10); type(a) <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'> sage: lift(a) 751 sage: a.lift() 751
- sqrt(extend=True, all=False)#
Return square root or square roots of
self
modulo \(n\).INPUT:
extend
- bool (default:True
); ifTrue
, return a square root in an extension ring, if necessary. Otherwise, raise aValueError
if the square root is not in the base ring.all
- bool (default:False
); ifTrue
, return {all} square roots of self, instead of just one.
ALGORITHM: Calculates the square roots mod \(p\) for each of the primes \(p\) dividing the order of the ring, then lifts them \(p\)-adically and uses the CRT to find a square root mod \(n\).
See also
square_root_mod_prime_power()
andsquare_root_mod_prime()
for more algorithmic details.EXAMPLES:
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: GF(107)(0).sqrt(all=True) [0]
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]
- class sage.rings.finite_rings.integer_mod.IntegerMod_int64#
Bases:
IntegerMod_abstract
Elements of \(\ZZ/n\ZZ\) for n small enough to be operated on in 64 bits
EXAMPLES:
sage: a = Mod(10,3^10); a 10 sage: type(a) <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'> sage: loads(a.dumps()) == a True sage: Mod(5, 2^31) 5
AUTHORS:
Robert Bradshaw (2006-09-14)
- gcd(other)#
Greatest common divisor
Returns the “smallest” generator in \(\ZZ / N\ZZ\) of the ideal generated by
self
andother
.INPUT:
other
– an element of the same ring as this one.
EXAMPLES:
sage: mod(2^3*3^2*5, 3^3*2^2*17^5).gcd(mod(2^4*3*17, 3^3*2^2*17^5)) 12 sage: mod(0,17^5).gcd(mod(0,17^5)) 0
- is_one()#
Returns
True
if this is \(1\), otherwiseFalse
.EXAMPLES:
sage: (mod(-1,5^10)^2).is_one() True sage: mod(0,5^10).is_one() False
- is_unit()#
Return True iff this element is a unit.
EXAMPLES:
sage: mod(13, 5^10).is_unit() True sage: mod(25, 5^10).is_unit() False
- lift()#
Lift an integer modulo \(n\) to the integers.
EXAMPLES:
sage: a = Mod(8943, 2^25); type(a) <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'> sage: lift(a) 8943 sage: a.lift() 8943
- class sage.rings.finite_rings.integer_mod.IntegerMod_to_Integer#
Bases:
Map
Map to lift elements to
Integer
.EXAMPLES:
sage: ZZ.convert_map_from(GF(2)) Lifting map: From: Finite Field of size 2 To: Integer Ring
- class sage.rings.finite_rings.integer_mod.IntegerMod_to_IntegerMod#
Bases:
IntegerMod_hom
Very fast IntegerMod to IntegerMod homomorphism.
EXAMPLES:
sage: from sage.rings.finite_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] [<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>, <class 'sage.rings.finite_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]
- is_injective()#
Return whether this morphism is injective.
EXAMPLES:
sage: Zmod(4).hom(Zmod(2)).is_injective() False
- is_surjective()#
Return whether this morphism is surjective.
EXAMPLES:
sage: Zmod(4).hom(Zmod(2)).is_surjective() True
- class sage.rings.finite_rings.integer_mod.Integer_to_IntegerMod#
Bases:
IntegerMod_hom
Fast \(\ZZ \rightarrow \ZZ/n\ZZ\) morphism.
EXAMPLES:
We make sure it works for every type.
sage: from sage.rings.finite_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] [<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <class 'sage.rings.finite_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]
- is_injective()#
Return whether this morphism is injective.
EXAMPLES:
sage: ZZ.hom(Zmod(2)).is_injective() False
- is_surjective()#
Return whether this morphism is surjective.
EXAMPLES:
sage: ZZ.hom(Zmod(2)).is_surjective() True
- section()#
- sage.rings.finite_rings.integer_mod.Mod(n, m, parent=None)#
Return the equivalence class of \(n\) modulo \(m\) as an element of \(\ZZ/m\ZZ\).
EXAMPLES:
sage: x = Mod(12345678, 32098203845329048) sage: x 12345678 sage: x^100 1017322209155072
You can also use the lowercase version:
sage: mod(12,5) 2
Illustrates that trac ticket #5971 is fixed. Consider \(n\) modulo \(m\) when \(m = 0\). Then \(\ZZ/0\ZZ\) is isomorphic to \(\ZZ\) so \(n\) modulo \(0\) is equivalent to \(n\) for any integer value of \(n\):
sage: Mod(10, 0) 10 sage: a = randint(-100, 100) sage: Mod(a, 0) == a True
- class sage.rings.finite_rings.integer_mod.NativeIntStruct#
Bases:
object
We store the various forms of the modulus here rather than in the parent for efficiency reasons.
We may also store a cached table of all elements of a given ring in this class.
- inverses#
- precompute_table(parent)#
Function to compute and cache all elements of this class.
If
inverses == True
, also computes and caches the inverses of the invertible elements.EXAMPLES:
sage: from sage.rings.finite_rings.integer_mod import NativeIntStruct sage: R = IntegerModRing(10) sage: M = NativeIntStruct(R.order()) sage: M.precompute_table(R) sage: M.table [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: M.inverses [None, 1, None, 7, None, None, None, 3, None, 9]
This is used by the
sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic
constructor:sage: from sage.rings.finite_rings.integer_mod_ring import IntegerModRing_generic sage: R = IntegerModRing_generic(39, cache=False) sage: R(5)^-1 8 sage: R(5)^-1 is R(8) False sage: R = IntegerModRing_generic(39, cache=True) # indirect doctest sage: R(5)^-1 is R(8) True
Check that the inverse of 0 modulo 1 works, see trac ticket #13639:
sage: R = IntegerModRing_generic(1, cache=True) # indirect doctest sage: R(0)^-1 is R(0) True
- table#
- sage.rings.finite_rings.integer_mod.is_IntegerMod(x)#
Return
True
if and only if x is an integer modulo \(n\).EXAMPLES:
sage: from sage.rings.finite_rings.integer_mod import is_IntegerMod sage: is_IntegerMod(5) False sage: is_IntegerMod(Mod(5,10)) True
- sage.rings.finite_rings.integer_mod.lucas(k, P, Q=1, n=None)#
Return \([V_k(P, Q) \mod n, Q^{\lfloor k/2 \rfloor} \mod n]\) where \(V_k\) is the Lucas function defined by the recursive relation
\[V_k(P, Q) = P V_{k-1}(P, Q) - Q V_{k-2}(P, Q)\]with \(V_0 = 2, V_1 = P\).
INPUT:
k
– integer; index to computeP
,Q
– integers or modular integers; initial valuesn
– integer (optional); modulus to use ifP
is not a modular integer
REFERENCES:
AUTHORS:
Somindu Chaya Ramanna, Shashank Singh and Srinivas Vivek Venkatesh (2011-09-15, ECC2011 summer school)
Robert Bradshaw
EXAMPLES:
sage: [lucas(k,4,5,11)[0] for k in range(30)] [2, 4, 6, 4, 8, 1, 8, 5, 2, 5, 10, 4, 10, 9, 8, 9, 7, 5, 7, 3, 10, 3, 6, 9, 6, 1, 7, 1, 2, 3] sage: lucas(20,4,5,11) [10, 1]
- sage.rings.finite_rings.integer_mod.lucas_q1(mm, P)#
Return \(V_k(P, 1)\) where \(V_k\) is the Lucas function defined by the recursive relation
\(V_k(P, Q) = PV_{k-1}(P, Q) - QV_{k-2}(P, Q)\)
with \(V_0 = 2, V_1(P_Q) = P\).
REFERENCES:
AUTHORS:
Robert Bradshaw
- sage.rings.finite_rings.integer_mod.makeNativeIntStruct#
alias of
NativeIntStruct
- sage.rings.finite_rings.integer_mod.mod(n, m, parent=None)#
Return the equivalence class of \(n\) modulo \(m\) as an element of \(\ZZ/m\ZZ\).
EXAMPLES:
sage: x = Mod(12345678, 32098203845329048) sage: x 12345678 sage: x^100 1017322209155072
You can also use the lowercase version:
sage: mod(12,5) 2
Illustrates that trac ticket #5971 is fixed. Consider \(n\) modulo \(m\) when \(m = 0\). Then \(\ZZ/0\ZZ\) is isomorphic to \(\ZZ\) so \(n\) modulo \(0\) is equivalent to \(n\) for any integer value of \(n\):
sage: Mod(10, 0) 10 sage: a = randint(-100, 100) sage: Mod(a, 0) == a True
- sage.rings.finite_rings.integer_mod.square_root_mod_prime(a, p=None)#
Calculates the square root of \(a\), where \(a\) is an integer mod \(p\); if \(a\) is not a perfect square, this returns an (incorrect) answer without checking.
ALGORITHM: Several cases based on residue class of \(p \bmod 16\).
\(p \bmod 2 = 0\): \(p = 2\) so \(\sqrt{a} = a\).
\(p \bmod 4 = 3\): \(\sqrt{a} = a^{(p+1)/4}\).
\(p \bmod 8 = 5\): \(\sqrt{a} = \zeta i a\) where \(\zeta = (2a)^{(p-5)/8}\), \(i=\sqrt{-1}\).
\(p \bmod 16 = 9\): Similar, work in a bi-quadratic extension of \(\GF{p}\) for small \(p\), Tonelli and Shanks for large \(p\).
\(p \bmod 16 = 1\): Tonelli and Shanks.
REFERENCES:
AUTHORS:
Robert Bradshaw
- sage.rings.finite_rings.integer_mod.square_root_mod_prime_power(a, p, e)#
Calculates the square root of \(a\), where \(a\) is an integer mod \(p^e\).
ALGORITHM: Compute \(p\)-adically by stripping off even powers of \(p\) to get a unit and lifting \(\sqrt{unit} \bmod p\) via Newton’s method whenever \(p\) is odd and by a variant of Hensel lifting for \(p = 2\).
AUTHORS:
Robert Bradshaw
Lorenz Panny (2022): polynomial-time algorithm for \(p = 2\)
EXAMPLES:
sage: from sage.rings.finite_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 sage: mod(100, 5^7).sqrt()^2 100