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 a int_fast32_t (typically an int); this is used if the modulus is less than \(\sqrt{2^{31}-1}\).

  • IntegerMod_int64 stores its value in a int_fast64_t (typically a long 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 an unsigned long.

  • IntegerMod_gmp stores its value in a mpz_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[source]#

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]

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import Int_to_IntegerMod
>>> Rs = [Integers(Integer(2)**k) for k in range(Integer(1),Integer(50),Integer(10))]
>>> [type(R(Integer(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'>]
>>> fs = [Int_to_IntegerMod(R) for R in Rs]
>>> [f(-Integer(1)) for f in fs]
[1, 2047, 2097151, 2147483647, 2199023255551]
sage.rings.finite_rings.integer_mod.IntegerMod(parent, value)[source]#

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

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import IntegerMod
>>> R = IntegerModRing(Integer(100))
>>> type(R._pyx_order.table)
<class 'list'>
>>> IntegerMod(R, Integer(42))
42
>>> IntegerMod(R, Integer(142))
42
>>> IntegerMod(R, Integer(10)**Integer(100) + Integer(42))
42
>>> IntegerMod(R, -Integer(9158))
42
class sage.rings.finite_rings.integer_mod.IntegerMod_abstract[source]#

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

>>> from sage.all import *
>>> a = Mod(Integer(10), Integer(30)**Integer(10)); a
10
>>> type(a)
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
>>> loads(a.dumps()) == a
True
additive_order()[source]#

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

>>> from sage.all import *
>>> Integers(Integer(20))(Integer(2)).additive_order()
10
>>> Integers(Integer(20))(Integer(7)).additive_order()
20
>>> Integers(Integer(90308402384902))(Integer(2)).additive_order()
45154201192451
charpoly(var='x')[source]#

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

>>> from sage.all import *
>>> k = GF(Integer(3))
>>> a = k.gen()
>>> a.charpoly('x')
x + 2
>>> a + Integer(2)
0

AUTHORS:

  • Craig Citro

crt(other)[source]#

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.

EXAMPLES:

sage: a = mod(3, 5)
sage: b = mod(2, 7)
sage: a.crt(b)
23

>>> from sage.all import *
>>> a = mod(Integer(3), Integer(5))
>>> b = mod(Integer(2), Integer(7))
>>> a.crt(b)
23

sage: a = mod(37, 10^8)
sage: b = mod(9, 3^8)
sage: a.crt(b)
125900000037

>>> from sage.all import *
>>> a = mod(Integer(37), Integer(10)**Integer(8))
>>> b = mod(Integer(9), Integer(3)**Integer(8))
>>> a.crt(b)
125900000037

sage: b = mod(0, 1)
sage: a.crt(b) == a
True
sage: a.crt(b).modulus()
100000000

>>> from sage.all import *
>>> b = mod(Integer(0), Integer(1))
>>> a.crt(b) == a
True
>>> a.crt(b).modulus()
100000000

AUTHORS:

  • Robert Bradshaw

divides(other)[source]#

Test whether self divides other.

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

>>> from sage.all import *
>>> R = Zmod(Integer(6))
>>> R(Integer(2)).divides(R(Integer(4)))
True
>>> R(Integer(4)).divides(R(Integer(2)))
True
>>> R(Integer(2)).divides(R(Integer(3)))
False
generalised_log()[source]#

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                                            # needs sage.libs.pari sage.modules
[1, 3, 1]
sage: prod([Zmod(1568).unit_gens()[i] ** v[i] for i in [0..2]])             # needs sage.libs.pari sage.modules
3

>>> from sage.all import *
>>> m = Mod(Integer(3), Integer(1568))
>>> v = m.generalised_log(); v                                            # needs sage.libs.pari sage.modules
[1, 3, 1]
>>> prod([Zmod(Integer(1568)).unit_gens()[i] ** v[i] for i in (ellipsis_range(Integer(0),Ellipsis,Integer(2)))])             # needs sage.libs.pari sage.modules
3

See also

The method log().

Warning

The output is given relative to the set of generators obtained by passing algorithm='sage' to the method unit_gens() of the parent (which is the default). Specifying algorithm='pari' usually yields a different set of generators that is incompatible with this method.

is_nilpotent()[source]#

Return True if self is nilpotent, i.e., some power of self is zero.

EXAMPLES:

sage: a = Integers(90384098234^3)
sage: factor(a.order())                                                     # needs sage.libs.pari
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

>>> from sage.all import *
>>> a = Integers(Integer(90384098234)**Integer(3))
>>> factor(a.order())                                                     # needs sage.libs.pari
2^3 * 191^3 * 236607587^3
>>> b = a(Integer(2)*Integer(191))
>>> b.is_nilpotent()
False
>>> b = a(Integer(2)*Integer(191)*Integer(236607587))
>>> 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()[source]#
is_primitive_root()[source]#

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()                                        # needs sage.libs.pari
True
sage: mod(11, 1009^2).is_primitive_root()                                   # needs sage.libs.pari
True

>>> from sage.all import *
>>> mod(Integer(1), Integer(2)).is_primitive_root()
True
>>> mod(Integer(3), Integer(4)).is_primitive_root()
True
>>> mod(Integer(2), Integer(7)).is_primitive_root()
False
>>> mod(Integer(3), Integer(98)).is_primitive_root()                                        # needs sage.libs.pari
True
>>> mod(Integer(11), Integer(1009)**Integer(2)).is_primitive_root()                                   # needs sage.libs.pari
True
is_square()[source]#

EXAMPLES:

sage: Mod(3, 17).is_square()
False

sage: # needs sage.libs.pari
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

>>> from sage.all import *
>>> Mod(Integer(3), Integer(17)).is_square()
False

>>> # needs sage.libs.pari
>>> Mod(Integer(9), Integer(17)).is_square()
True
>>> Mod(Integer(9), Integer(17)*Integer(19)**Integer(2)).is_square()
True
>>> Mod(-Integer(1), Integer(17)**Integer(30)).is_square()
True
>>> Mod(Integer(1)/Integer(9), next_prime(Integer(2)**Integer(40))).is_square()
True
>>> Mod(Integer(1)/Integer(25), next_prime(Integer(2)**Integer(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()[source]#
lift_centered()[source]#

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

>>> from sage.all import *
>>> Mod(Integer(0),Integer(5)).lift_centered()
0
>>> Mod(Integer(1),Integer(5)).lift_centered()
1
>>> Mod(Integer(2),Integer(5)).lift_centered()
2
>>> Mod(Integer(3),Integer(5)).lift_centered()
-2
>>> Mod(Integer(4),Integer(5)).lift_centered()
-1
>>> Mod(Integer(50),Integer(100)).lift_centered()
50
>>> Mod(Integer(51),Integer(100)).lift_centered()
-49
>>> Mod(-Integer(1),Integer(3)**Integer(100)).lift_centered()
-1
log(b=None)[source]#

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\). If b is not given, R.multiplicative_generator() is used, where R is the parent of self.

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 pari:znlog function for each odd prime power in the factorization of the modulus. This method can be quite slow for large moduli.

EXAMPLES:

sage: # needs sage.libs.pari sage.modules
sage: r = Integers(125)
sage: b = r.multiplicative_generator()^3
sage: a = b^17
sage: a.log(b)
17
sage: a.log()
51

>>> from sage.all import *
>>> # needs sage.libs.pari sage.modules
>>> r = Integers(Integer(125))
>>> b = r.multiplicative_generator()**Integer(3)
>>> a = b**Integer(17)
>>> a.log(b)
17
>>> a.log()
51

A bigger example:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> FF = FiniteField(Integer(2)**Integer(32) + Integer(61))
>>> c = FF(Integer(4294967356))
>>> x = FF(Integer(2))
>>> a = c.log(x)
>>> a
2147483678
>>> 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)                     # needs sage.libs.pari
5735816763073854953388147237921

>>> from sage.all import *
>>> m = Integer(2)**Integer(99) * Integer(77)**Integer(7) * Integer(123456789) * Integer(13712923537615486607)**Integer(2)
>>> (Mod(Integer(5),m)**Integer(5735816763073854953388147237921)).log(Integer(5))                     # needs sage.libs.pari
5735816763073854953388147237921

Errors are generated if the logarithm doesn’t exist or the inputs are not units:

sage: Mod(3, 7).log(Mod(2, 7))                                              # needs sage.libs.pari
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

>>> from sage.all import *
>>> Mod(Integer(3), Integer(7)).log(Mod(Integer(2), Integer(7)))                                              # needs sage.libs.pari
Traceback (most recent call last):
...
ValueError: no logarithm of 3 found to base 2 modulo 7
>>> a = Mod(Integer(16), Integer(100)); b = Mod(Integer(4), Integer(100))
>>> 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')[source]#

Returns the minimal polynomial of this element.

EXAMPLES:

sage: GF(241, 'a')(1).minimal_polynomial(var = 'z')
z + 240

>>> from sage.all import *
>>> GF(Integer(241), 'a')(Integer(1)).minimal_polynomial(var = 'z')
z + 240
minpoly(var='x')[source]#

Returns the minimal polynomial of this element.

EXAMPLES:

sage: GF(241, 'a')(1).minpoly()
x + 240

>>> from sage.all import *
>>> GF(Integer(241), 'a')(Integer(1)).minpoly()
x + 240
modulus()[source]#

EXAMPLES:

sage: Mod(3,17).modulus()
17

>>> from sage.all import *
>>> Mod(Integer(3),Integer(17)).modulus()
17
multiplicative_order()[source]#

Returns the multiplicative order of self.

EXAMPLES:

sage: Mod(-1, 5).multiplicative_order()                                     # needs sage.libs.pari
2
sage: Mod(1, 5).multiplicative_order()                                      # needs sage.libs.pari
1
sage: Mod(0, 5).multiplicative_order()                                      # needs sage.libs.pari
Traceback (most recent call last):
...
ArithmeticError: multiplicative order of 0 not defined
since it is not a unit modulo 5

>>> from sage.all import *
>>> Mod(-Integer(1), Integer(5)).multiplicative_order()                                     # needs sage.libs.pari
2
>>> Mod(Integer(1), Integer(5)).multiplicative_order()                                      # needs sage.libs.pari
1
>>> Mod(Integer(0), Integer(5)).multiplicative_order()                                      # needs sage.libs.pari
Traceback (most recent call last):
...
ArithmeticError: multiplicative order of 0 not defined
since it is not a unit modulo 5
norm()[source]#

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

>>> from sage.all import *
>>> k = GF(Integer(691))
>>> a = k(Integer(389))
>>> a.norm()
389

AUTHORS:

  • Craig Citro

nth_root(n, extend=False, all=False, algorithm=None, cunningham=False)[source]#

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); if True, return all \(n\)th roots of self, 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 of n is computed. If cunningham is set to True, the factorization of n 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 line sage -i cunningham_tables

OUTPUT:

If self has an \(n\)th root, returns one (if all is False) or a list of all of them (if all is True). Otherwise, raises a ValueError (if extend is False) or a NotImplementedError (if extend is True).

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 returned

      • otherwise; 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: # needs sage.rings.padics
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]

>>> from sage.all import *
>>> K = GF(Integer(31))
>>> a = K(Integer(22))
>>> K(Integer(22)).nth_root(Integer(7))
13
>>> K(Integer(25)).nth_root(Integer(5))
5
>>> K(Integer(23)).nth_root(Integer(3))
29

>>> # needs sage.rings.padics
>>> mod(Integer(225), Integer(2)**Integer(5)*Integer(3)**Integer(2)).nth_root(Integer(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]
>>> mod(Integer(275), Integer(2)**Integer(5)*Integer(7)**Integer(4)).nth_root(Integer(7), all=True)
[58235, 25307, 69211, 36283, 3355, 47259, 14331]
>>> mod(Integer(1),Integer(8)).nth_root(Integer(2), all=True)
[1, 7, 5, 3]
>>> mod(Integer(4),Integer(8)).nth_root(Integer(2), all=True)
[2, 6]
>>> mod(Integer(1),Integer(16)).nth_root(Integer(4), all=True)
[1, 15, 13, 3, 9, 7, 5, 11]

>>> (mod(Integer(22),Integer(31))**Integer(200)).nth_root(Integer(200))
5
>>> mod(Integer(3),Integer(6)).nth_root(Integer(0), all=True)
[]
>>> mod(Integer(3),Integer(6)).nth_root(Integer(0))
Traceback (most recent call last):
...
ValueError
>>> mod(Integer(1),Integer(6)).nth_root(Integer(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')[source]#

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())                                                  # needs sage.libs.flint
<class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

>>> from sage.all import *
>>> k = GF(Integer(7))
>>> a = k.gen(); a
1
>>> a.polynomial()
1
>>> type(a.polynomial())                                                  # needs sage.libs.flint
<class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
rational_reconstruction()[source]#

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

>>> from sage.all import *
>>> R = IntegerModRing(Integer(97))
>>> a = R(Integer(2)) / R(Integer(3))
>>> a
33
>>> 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

>>> from sage.all import *
>>> k = GF(Integer(97))
>>> a = k(RationalField()('2/3'))
>>> a
33
>>> a.rational_reconstruction()
2/3
sqrt(extend=True, all=False)[source]#

Return square root or square roots of self modulo \(n\).

INPUT:

  • extend – bool (default: 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.

  • all – bool (default: False); if True, 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() and square_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: # needs sage.libs.pari
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

>>> from sage.all import *
>>> mod(-Integer(1), Integer(17)).sqrt()
4
>>> mod(Integer(5), Integer(389)).sqrt()
86
>>> mod(Integer(7), Integer(18)).sqrt()
5

>>> # needs sage.libs.pari
>>> a = mod(Integer(14), Integer(5)**Integer(60)).sqrt()
>>> a*a
14
>>> mod(Integer(15), Integer(389)).sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
>>> Mod(Integer(1)/Integer(9), next_prime(Integer(2)**Integer(40))).sqrt()**(-Integer(2))
9
>>> Mod(Integer(1)/Integer(25), next_prime(Integer(2)**Integer(90))).sqrt()**(-Integer(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

>>> from sage.all import *
>>> a = Mod(Integer(3), Integer(5)); a
3
>>> x = Mod(-Integer(1), Integer(360))
>>> x.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
>>> y = x.sqrt(); y
sqrt359
>>> y.parent()
Univariate Quotient Polynomial Ring in sqrt359 over
 Ring of integers modulo 360 with modulus x^2 + 1
>>> y**Integer(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]

>>> from sage.all import *
>>> R = Integers(Integer(5)*Integer(2)**Integer(3)*Integer(3)**Integer(2)); R
Ring of integers modulo 360
>>> R(Integer(40)).sqrt(all=True)
[20, 160, 200, 340]
>>> [x for x in R if x**Integer(2) == Integer(40)]  # Brute force verification
[20, 160, 200, 340]
>>> R(Integer(1)).sqrt(all=True)
[1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359]
>>> R(Integer(0)).sqrt(all=True)
[0, 60, 120, 180, 240, 300]

sage: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = Integers(Integer(5)*Integer(13)**Integer(3)*Integer(37)); R
Ring of integers modulo 406445
>>> v = R(-Integer(1)).sqrt(all=True); v
[78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592]
>>> [x**Integer(2) for x in v]
[406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444]
>>> v = R(Integer(169)).sqrt(all=True); min(v), -max(v), len(v)
(13, 13, 104)
>>> all(x**Integer(2) == Integer(169) for x in v)
True

sage: # needs sage.rings.finite_rings
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)
[]

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> t = FiniteField(next_prime(Integer(2)**Integer(100)))(Integer(4))
>>> t.sqrt(extend=False, all=True)
[2, 1267650600228229401496703205651]
>>> t = FiniteField(next_prime(Integer(2)**Integer(100)))(Integer(2))
>>> 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]

>>> from sage.all import *
>>> R = Integers(Integer(2)**Integer(7)); R
Ring of integers modulo 128
>>> a = R(Integer(17))
>>> a.sqrt()
23
>>> a.sqrt(all=True)
[23, 41, 87, 105]
>>> [x for x in R if x**Integer(2)==Integer(17)]
[23, 41, 87, 105]
square_root(extend=True, all=False)[source]#

Return square root or square roots of self modulo \(n\).

INPUT:

  • extend – bool (default: 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.

  • all – bool (default: False); if True, 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() and square_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: # needs sage.libs.pari
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

>>> from sage.all import *
>>> mod(-Integer(1), Integer(17)).sqrt()
4
>>> mod(Integer(5), Integer(389)).sqrt()
86
>>> mod(Integer(7), Integer(18)).sqrt()
5

>>> # needs sage.libs.pari
>>> a = mod(Integer(14), Integer(5)**Integer(60)).sqrt()
>>> a*a
14
>>> mod(Integer(15), Integer(389)).sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
>>> Mod(Integer(1)/Integer(9), next_prime(Integer(2)**Integer(40))).sqrt()**(-Integer(2))
9
>>> Mod(Integer(1)/Integer(25), next_prime(Integer(2)**Integer(90))).sqrt()**(-Integer(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

>>> from sage.all import *
>>> a = Mod(Integer(3), Integer(5)); a
3
>>> x = Mod(-Integer(1), Integer(360))
>>> x.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
>>> y = x.sqrt(); y
sqrt359
>>> y.parent()
Univariate Quotient Polynomial Ring in sqrt359 over
 Ring of integers modulo 360 with modulus x^2 + 1
>>> y**Integer(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]

>>> from sage.all import *
>>> R = Integers(Integer(5)*Integer(2)**Integer(3)*Integer(3)**Integer(2)); R
Ring of integers modulo 360
>>> R(Integer(40)).sqrt(all=True)
[20, 160, 200, 340]
>>> [x for x in R if x**Integer(2) == Integer(40)]  # Brute force verification
[20, 160, 200, 340]
>>> R(Integer(1)).sqrt(all=True)
[1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359]
>>> R(Integer(0)).sqrt(all=True)
[0, 60, 120, 180, 240, 300]

sage: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = Integers(Integer(5)*Integer(13)**Integer(3)*Integer(37)); R
Ring of integers modulo 406445
>>> v = R(-Integer(1)).sqrt(all=True); v
[78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592]
>>> [x**Integer(2) for x in v]
[406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444]
>>> v = R(Integer(169)).sqrt(all=True); min(v), -max(v), len(v)
(13, 13, 104)
>>> all(x**Integer(2) == Integer(169) for x in v)
True

sage: # needs sage.rings.finite_rings
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)
[]

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> t = FiniteField(next_prime(Integer(2)**Integer(100)))(Integer(4))
>>> t.sqrt(extend=False, all=True)
[2, 1267650600228229401496703205651]
>>> t = FiniteField(next_prime(Integer(2)**Integer(100)))(Integer(2))
>>> 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]

>>> from sage.all import *
>>> R = Integers(Integer(2)**Integer(7)); R
Ring of integers modulo 128
>>> a = R(Integer(17))
>>> a.sqrt()
23
>>> a.sqrt(all=True)
[23, 41, 87, 105]
>>> [x for x in R if x**Integer(2)==Integer(17)]
[23, 41, 87, 105]
trace()[source]#

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

>>> from sage.all import *
>>> k = GF(Integer(691))
>>> a = k(Integer(389))
>>> a.trace()
389

AUTHORS:

  • Craig Citro

valuation(p)[source]#

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 (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

>>> from sage.all import *
>>> R = ZZ.quo(Integer(9))
>>> a = R(Integer(3))
>>> b = R(Integer(6))
>>> a.valuation(Integer(3))
1
>>> a.valuation(Integer(3)) + b.valuation(Integer(3))
2
>>> (a*b).valuation(Integer(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.

>>> from sage.all import *
>>> a.valuation(Integer(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[source]#

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)[source]#

Greatest common divisor

Returns the “smallest” generator in \(\ZZ / N\ZZ\) of the ideal generated by self and other.

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

>>> from sage.all import *
>>> mod(Integer(2)**Integer(3)*Integer(3)**Integer(2)*Integer(5), Integer(3)**Integer(3)*Integer(2)**Integer(2)*Integer(17)**Integer(8)).gcd(mod(Integer(2)**Integer(4)*Integer(3)*Integer(17), Integer(3)**Integer(3)*Integer(2)**Integer(2)*Integer(17)**Integer(8)))
12
>>> mod(Integer(0),Integer(17)**Integer(8)).gcd(mod(Integer(0),Integer(17)**Integer(8)))
0
is_one()[source]#

Returns True if this is \(1\), otherwise False.

EXAMPLES:

sage: mod(1,5^23).is_one()
True
sage: mod(0,5^23).is_one()
False

>>> from sage.all import *
>>> mod(Integer(1),Integer(5)**Integer(23)).is_one()
True
>>> mod(Integer(0),Integer(5)**Integer(23)).is_one()
False
is_unit()[source]#

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

>>> from sage.all import *
>>> mod(Integer(13), Integer(5)**Integer(23)).is_unit()
True
>>> mod(Integer(25), Integer(5)**Integer(23)).is_unit()
False
lift()[source]#

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

>>> from sage.all import *
>>> a = Mod(Integer(8943), Integer(2)**Integer(70)); type(a)
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
>>> lift(a)
8943
>>> a.lift()
8943
class sage.rings.finite_rings.integer_mod.IntegerMod_hom[source]#

Bases: Morphism

class sage.rings.finite_rings.integer_mod.IntegerMod_int[source]#

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

>>> from sage.all import *
>>> a = Mod(Integer(10),Integer(30)); a
10
>>> loads(a.dumps()) == a
True
gcd(other)[source]#

Greatest common divisor

Returns the “smallest” generator in \(\ZZ / N\ZZ\) of the ideal generated by self and other.

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

>>> from sage.all import *
>>> R = Zmod(Integer(60)); S = Zmod(Integer(72))
>>> a = R(Integer(40)).gcd(S(Integer(30))); a
2
>>> a.parent()
Ring of integers modulo 12
>>> b = R(Integer(17)).gcd(Integer(60)); b
1
>>> b.parent()
Ring of integers modulo 60

>>> mod(Integer(72)*Integer(5), Integer(3)**Integer(3)*Integer(2)**Integer(2)*Integer(17)**Integer(2)).gcd(mod(Integer(48)*Integer(17), Integer(3)**Integer(3)*Integer(2)**Integer(2)*Integer(17)**Integer(2)))
12
>>> mod(Integer(0),Integer(1)).gcd(mod(Integer(0),Integer(1)))
0
is_one()[source]#

Returns True if this is \(1\), otherwise False.

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

>>> from sage.all import *
>>> mod(Integer(6),Integer(5)).is_one()
True
>>> mod(Integer(0),Integer(5)).is_one()
False
>>> mod(Integer(1), Integer(1)).is_one()
True
>>> Zmod(Integer(1)).one().is_one()
True
is_unit()[source]#

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

>>> from sage.all import *
>>> a=Mod(Integer(23),Integer(100))
>>> a.is_unit()
True
>>> a=Mod(Integer(24),Integer(100))
>>> a.is_unit()
False
lift()[source]#

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

>>> from sage.all import *
>>> a = Mod(Integer(8943), Integer(2)**Integer(10)); type(a)
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
>>> lift(a)
751
>>> a.lift()
751
sqrt(extend=True, all=False)[source]#

Return square root or square roots of self modulo \(n\).

INPUT:

  • extend – bool (default: 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.

  • all – bool (default: False); if True, 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() and square_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: # needs sage.libs.pari
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

>>> from sage.all import *
>>> mod(-Integer(1), Integer(17)).sqrt()
4
>>> mod(Integer(5), Integer(389)).sqrt()
86
>>> mod(Integer(7), Integer(18)).sqrt()
5

>>> # needs sage.libs.pari
>>> a = mod(Integer(14), Integer(5)**Integer(60)).sqrt()
>>> a*a
14
>>> mod(Integer(15), Integer(389)).sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
>>> Mod(Integer(1)/Integer(9), next_prime(Integer(2)**Integer(40))).sqrt()**(-Integer(2))
9
>>> Mod(Integer(1)/Integer(25), next_prime(Integer(2)**Integer(90))).sqrt()**(-Integer(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

>>> from sage.all import *
>>> a = Mod(Integer(3),Integer(5)); a
3
>>> x = Mod(-Integer(1), Integer(360))
>>> x.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
>>> y = x.sqrt(); y
sqrt359
>>> y.parent()
Univariate Quotient Polynomial Ring in sqrt359
 over Ring of integers modulo 360 with modulus x^2 + 1
>>> y**Integer(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]

>>> from sage.all import *
>>> R = Integers(Integer(5)*Integer(2)**Integer(3)*Integer(3)**Integer(2)); R
Ring of integers modulo 360
>>> R(Integer(40)).sqrt(all=True)
[20, 160, 200, 340]
>>> [x for x in R if x**Integer(2) == Integer(40)]  # Brute force verification
[20, 160, 200, 340]
>>> R(Integer(1)).sqrt(all=True)
[1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359]
>>> R(Integer(0)).sqrt(all=True)
[0, 60, 120, 180, 240, 300]
>>> GF(Integer(107))(Integer(0)).sqrt(all=True)
[0]

sage: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = Integers(Integer(5)*Integer(13)**Integer(3)*Integer(37)); R
Ring of integers modulo 406445
>>> v = R(-Integer(1)).sqrt(all=True); v
[78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592]
>>> [x**Integer(2) for x in v]
[406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444]
>>> v = R(Integer(169)).sqrt(all=True); min(v), -max(v), len(v)
(13, 13, 104)
>>> all(x**Integer(2) == Integer(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]

>>> from sage.all import *
>>> R = Integers(Integer(2)**Integer(7)); R
Ring of integers modulo 128
>>> a = R(Integer(17))
>>> a.sqrt()
23
>>> a.sqrt(all=True)
[23, 41, 87, 105]
>>> [x for x in R if x**Integer(2)==Integer(17)]
[23, 41, 87, 105]
class sage.rings.finite_rings.integer_mod.IntegerMod_int64[source]#

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

>>> from sage.all import *
>>> a = Mod(Integer(10),Integer(3)**Integer(10)); a
10
>>> type(a)
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>
>>> loads(a.dumps()) == a
True
>>> Mod(Integer(5), Integer(2)**Integer(31))
5

AUTHORS:

  • Robert Bradshaw (2006-09-14)

gcd(other)[source]#

Greatest common divisor

Returns the “smallest” generator in \(\ZZ / N\ZZ\) of the ideal generated by self and other.

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

>>> from sage.all import *
>>> mod(Integer(2)**Integer(3)*Integer(3)**Integer(2)*Integer(5), Integer(3)**Integer(3)*Integer(2)**Integer(2)*Integer(17)**Integer(5)).gcd(mod(Integer(2)**Integer(4)*Integer(3)*Integer(17), Integer(3)**Integer(3)*Integer(2)**Integer(2)*Integer(17)**Integer(5)))
12
>>> mod(Integer(0),Integer(17)**Integer(5)).gcd(mod(Integer(0),Integer(17)**Integer(5)))
0
is_one()[source]#

Returns True if this is \(1\), otherwise False.

EXAMPLES:

sage: (mod(-1,5^10)^2).is_one()
True
sage: mod(0,5^10).is_one()
False

>>> from sage.all import *
>>> (mod(-Integer(1),Integer(5)**Integer(10))**Integer(2)).is_one()
True
>>> mod(Integer(0),Integer(5)**Integer(10)).is_one()
False
is_unit()[source]#

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

>>> from sage.all import *
>>> mod(Integer(13), Integer(5)**Integer(10)).is_unit()
True
>>> mod(Integer(25), Integer(5)**Integer(10)).is_unit()
False
lift()[source]#

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

>>> from sage.all import *
>>> a = Mod(Integer(8943), Integer(2)**Integer(25)); type(a)
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>
>>> lift(a)
8943
>>> a.lift()
8943
class sage.rings.finite_rings.integer_mod.IntegerMod_to_Integer[source]#

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

>>> from sage.all import *
>>> ZZ.convert_map_from(GF(Integer(2)))
Lifting map:
  From: Finite Field of size 2
  To:   Integer Ring
class sage.rings.finite_rings.integer_mod.IntegerMod_to_IntegerMod[source]#

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]

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import IntegerMod_to_IntegerMod
>>> Rs = [Integers(Integer(3)**k) for k in range(Integer(1),Integer(30),Integer(5))]
>>> [type(R(Integer(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'>]
>>> fs = [IntegerMod_to_IntegerMod(S, R)
...       for R in Rs for S in Rs if S is not R and S.order() > R.order()]
>>> all(f(-Integer(1)) == f.codomain()(-Integer(1)) for f in fs)
True
>>> [f(-Integer(1)) for f in fs]
[2, 2, 2, 2, 2, 728, 728, 728, 728, 177146, 177146, 177146, 43046720, 43046720, 10460353202]
is_injective()[source]#

Return whether this morphism is injective.

EXAMPLES:

sage: Zmod(4).hom(Zmod(2)).is_injective()
False

>>> from sage.all import *
>>> Zmod(Integer(4)).hom(Zmod(Integer(2))).is_injective()
False
is_surjective()[source]#

Return whether this morphism is surjective.

EXAMPLES:

sage: Zmod(4).hom(Zmod(2)).is_surjective()
True

>>> from sage.all import *
>>> Zmod(Integer(4)).hom(Zmod(Integer(2))).is_surjective()
True
class sage.rings.finite_rings.integer_mod.Integer_to_IntegerMod[source]#

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]

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import Integer_to_IntegerMod
>>> Rs = [Integers(Integer(10)), Integers(Integer(10)**Integer(5)), Integers(Integer(10)**Integer(10))]
>>> [type(R(Integer(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'>]
>>> fs = [Integer_to_IntegerMod(R) for R in Rs]
>>> [f(-Integer(1)) for f in fs]
[9, 99999, 9999999999]
is_injective()[source]#

Return whether this morphism is injective.

EXAMPLES:

sage: ZZ.hom(Zmod(2)).is_injective()
False

>>> from sage.all import *
>>> ZZ.hom(Zmod(Integer(2))).is_injective()
False
is_surjective()[source]#

Return whether this morphism is surjective.

EXAMPLES:

sage: ZZ.hom(Zmod(2)).is_surjective()
True

>>> from sage.all import *
>>> ZZ.hom(Zmod(Integer(2))).is_surjective()
True
section()[source]#
sage.rings.finite_rings.integer_mod.Mod(n, m, parent=None)[source]#

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

>>> from sage.all import *
>>> x = Mod(Integer(12345678), Integer(32098203845329048))
>>> x
12345678
>>> x**Integer(100)
1017322209155072

You can also use the lowercase version:

sage: mod(12,5)
2

>>> from sage.all import *
>>> mod(Integer(12),Integer(5))
2

Illustrates that Issue #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

>>> from sage.all import *
>>> Mod(Integer(10), Integer(0))
10
>>> a = randint(-Integer(100), Integer(100))
>>> Mod(a, Integer(0)) == a
True
class sage.rings.finite_rings.integer_mod.NativeIntStruct[source]#

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[source]#
precompute_table(parent)[source]#

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]

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import NativeIntStruct
>>> R = IntegerModRing(Integer(10))
>>> M = NativeIntStruct(R.order())
>>> M.precompute_table(R)
>>> M.table
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 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

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod_ring import IntegerModRing_generic
>>> R = IntegerModRing_generic(Integer(39), cache=False)
>>> R(Integer(5))**-Integer(1)
8
>>> R(Integer(5))**-Integer(1) is R(Integer(8))
False
>>> R = IntegerModRing_generic(Integer(39), cache=True)  # indirect doctest
>>> R(Integer(5))**-Integer(1) is R(Integer(8))
True

Check that the inverse of 0 modulo 1 works, see Issue #13639:

sage: R = IntegerModRing_generic(1, cache=True)  # indirect doctest
sage: R(0)^-1 is R(0)
True

>>> from sage.all import *
>>> R = IntegerModRing_generic(Integer(1), cache=True)  # indirect doctest
>>> R(Integer(0))**-Integer(1) is R(Integer(0))
True
table[source]#
sage.rings.finite_rings.integer_mod.is_IntegerMod(x)[source]#

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)
doctest:warning...
DeprecationWarning: The function is_IntegerMod is deprecated;
use 'isinstance(..., IntegerMod_abstract)' instead.
See https://github.com/sagemath/sage/issues/38128 for details.
False
sage: is_IntegerMod(Mod(5,10))
True

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import is_IntegerMod
>>> is_IntegerMod(Integer(5))
doctest:warning...
DeprecationWarning: The function is_IntegerMod is deprecated;
use 'isinstance(..., IntegerMod_abstract)' instead.
See https://github.com/sagemath/sage/issues/38128 for details.
False
>>> is_IntegerMod(Mod(Integer(5),Integer(10)))
True
sage.rings.finite_rings.integer_mod.lucas(k, P, Q=1, n=None)[source]#

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 compute

  • P, Q – integers or modular integers; initial values

  • n – integer (optional); modulus to use if P 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]

>>> from sage.all import *
>>> [lucas(k,Integer(4),Integer(5),Integer(11))[Integer(0)] for k in range(Integer(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]

>>> lucas(Integer(20),Integer(4),Integer(5),Integer(11))
[10, 1]
sage.rings.finite_rings.integer_mod.lucas_q1(mm, P)[source]#

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[source]#

alias of NativeIntStruct

sage.rings.finite_rings.integer_mod.mod(n, m, parent=None)[source]#

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

>>> from sage.all import *
>>> x = Mod(Integer(12345678), Integer(32098203845329048))
>>> x
12345678
>>> x**Integer(100)
1017322209155072

You can also use the lowercase version:

sage: mod(12,5)
2

>>> from sage.all import *
>>> mod(Integer(12),Integer(5))
2

Illustrates that Issue #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

>>> from sage.all import *
>>> Mod(Integer(10), Integer(0))
10
>>> a = randint(-Integer(100), Integer(100))
>>> Mod(a, Integer(0)) == a
True
sage.rings.finite_rings.integer_mod.square_root_mod_prime(a, p=None)[source]#

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)[source]#

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

>>> from sage.all import *
>>> from sage.rings.finite_rings.integer_mod import square_root_mod_prime_power
>>> a = Mod(Integer(17),Integer(2)**Integer(20))
>>> b = square_root_mod_prime_power(a,Integer(2),Integer(20))
>>> b**Integer(2) == a
True

sage: a = Mod(72, 97^10)
sage: b = square_root_mod_prime_power(a, 97, 10)                                # needs sage.libs.pari
sage: b^2 == a                                                                  # needs sage.libs.pari
True
sage: mod(100, 5^7).sqrt()^2                                                    # needs sage.libs.pari
100

>>> from sage.all import *
>>> a = Mod(Integer(72), Integer(97)**Integer(10))
>>> b = square_root_mod_prime_power(a, Integer(97), Integer(10))                                # needs sage.libs.pari
>>> b**Integer(2) == a                                                                  # needs sage.libs.pari
True
>>> mod(Integer(100), Integer(5)**Integer(7)).sqrt()**Integer(2)                                                    # needs sage.libs.pari
100