24.4 Elements of $ \mathbf{Z}/n\mathbf{Z}$

Module: sage.rings.integer_mod

Elements of $ \mathbf{Z}/n\mathbf{Z}$

An element of the integers modulo $ n$ .

There are three types of integer_mod classes, depending on the size of the 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

IntegerMod( )

Create an integer modulo $ n$ with the given parent.

This is mainly for internal use.

Mod( )

Return the equivalence class of $ n$ modulo $ m$ as an element of $ \mathbf{Z}/m\mathbf{Z}$ .

sage: x = Mod(12345678, 32098203845329048)
sage: x
12345678
sage: x^100
1017322209155072

You can also use the lowercase version:

sage: mod(12,5)
2

fast_lucas( )

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

is_IntegerMod( )

Return True if and only if x is an integer modulo $ n$ .

sage: is_IntegerMod(5)
False
sage: is_IntegerMod(Mod(5,10))
True

makeNativeIntStruct( )

Function to convert a Sage Integer into class NativeIntStruct.

NOTE: This function seems completely redundant, and is not used anywhere.

mod( )

Return the equivalence class of $ n$ modulo $ m$ as an element of $ \mathbf{Z}/m\mathbf{Z}$ .

sage: x = Mod(12345678, 32098203845329048)
sage: x
12345678
sage: x^100
1017322209155072

You can also use the lowercase version:

sage: mod(12,5)
2

slow_lucas( )

Lucas function defined using the standard definition, for consistency testing.

square_root_mod_prime( )

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$ .

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

square_root_mod_prime_power( )

Calculates the square root of $ a$ , where $ a$ is an integer mod $ p^e$ .

ALGORITHM: Perform $ p$ -adically by stripping off even powers of $ p$ to get a unit and lifting $ \sqrt{unit} \bmod p$ 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

class Int_to_IntegerMod
We make sure it works for every type.
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

_repr_type( )

Class: Integer_to_IntegerMod

class Integer_to_IntegerMod
Fast $ \mathbf{Z}\rightarrow \mathbf{Z}/n\mathbf{Z}$ morphism.

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

_repr_type( )

Class: IntegerMod_abstract

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

additive_order( )

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

charpoly( )

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

crt( )

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

is_nilpotent( )

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 $ m \geq \log_2(n)$ , where $ n$ is the modulus. Then $ x \in \mathbf{Z}/n\mathbf{Z}$ 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_square( )

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 $ (\code{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 \vert\vert n$ , then $ ord_p(\code{self})$ must be even or greater than $ k$ .

The case $ p=2$ is handled separately.

Author: Robert Bradshaw

log( )

Return an integer $ x$ such that $ b^x = a$ , where $ a$ is self.

Input:

self
- unit modulo $ n$
b
- a generator of the multiplicative group 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$ .

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:

modulus( )

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

multiplicative_order( )

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

norm( )

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

nth_root( )

Returns an $ n$ th root of self.

Input:

n
- integer $ \geq 1$ (must fit in C int type)
all
- bool (default: False); if True, return all $ n$ th roots of self, instead of just one.

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.

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]

polynomial( )

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

rational_reconstruction( )

sage: R = IntegerModRing(97)
sage: a = R(2) / R(3)
sage: a
33
sage: a.rational_reconstruction()
2/3

sqrt( )

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

square_root( )

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

trace( )

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_

__abs__( )

Raise an error message, since abs(x) makes no sense when x is an integer modulo $ n$ .

sage: abs(Mod(2,3))
Traceback (most recent call last):
...
ArithmeticError: absolute valued not defined on integers modulo n.

__reduce__( )

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

_balanced_abs( )

This function returns $ x$ or $ -x$ , whichever has a positive representative in $ -n/2 < x \leq n/2$ .

This is used so that the same square root is always returned, despite the possibly probabalistic nature of the underlying algorithm.

_gap_init_( )

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 $ \leq 65536$ .

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)

_integer_( )

_latex_( )

_magma_init_( )

Coercion to Magma.

sage: a = Integers(15)(4)       
sage: b = magma(a)                # optional
sage: b.Type()                    # optional
RngIntResElt
sage: b^2                         # optional
1

_pari_init_( )

_rational_( )

_repr_( )

Class: IntegerMod_gmp

class IntegerMod_gmp
Elements of $ \mathbf{Z}/n\mathbf{Z}$ for n not small enough to be operated on in word size.

Author: Robert Bradshaw (2006-08-24)

Functions: is_one,$ \,$ is_unit,$ \,$ lift

is_one( )

Returns True if this is $ 1$ , otherwise False.

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.

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.

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__

__copy__( )

__crt( )

__float__( )

__index__( )

Needed so integers modulo $ n$ can be used as list indices.

sage: v = [1,2,3,4,5]
sage: v[Mod(3,10^20)]
4

__int__( )

__invert__( )

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.

__long__( )

__lshift__( )

Multiply self by $ 2^$right quickly via bit shifting and modulus.

sage: e = Mod(19, 10^10)
sage: e << 102
9443608576

__mod__( )

__rshift__( )

Return self shifted right by right bits. (In $ \mathbf{Z}/n\mathbf{Z}$ , 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

class IntegerMod_hom

Special Functions: __init__

Class: IntegerMod_int

class IntegerMod_int
Elements of $ \mathbf{Z}/n\mathbf{Z}$ for n small enough to be operated on in 32 bits

Author: Robert Bradshaw (2006-08-24)

Functions: is_one,$ \,$ is_unit,$ \,$ lift,$ \,$ sqrt

is_one( )

Returns True if this is $ 1$ , otherwise False.

sage: mod(6,5).is_one()
True
sage: mod(0,5).is_one()
False

is_unit( )

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

Lift an integer modulo $ n$ 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

sqrt( )

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

__copy__( )

__crt( )

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

__float__( )

__index__( )

Needed so integers modulo $ n$ can be used as list indices.

sage: v = [1,2,3,4,5]
sage: v[Mod(10,7)]
4

__int__( )

__invert__( )

Return the multiplicative inverse of self.

sage: ~mod(7,100)
43

__long__( )

__lshift__( )

Multiply self by $ 2^$right very quickly via bit shifting.

sage: e = Mod(5, 2^10 - 1)
sage: e<<5
160
sage: e*2^5
160

__mod__( )

__rshift__( )

Divide self by $ 2^{ ext{right}}$ and take floor via bit shifting.

sage: e = Mod(8, 2^5 - 1)
sage: e >> 3
1
sage: int(e)/int(2^3)
1

_balanced_abs( )

This function returns $ x$ or $ -x$ , whichever has a positive representative in $ -n/2 < x \leq n/2$ .

_make_new_with_parent_c( )

Class: IntegerMod_int64

class IntegerMod_int64
Elements of $ \mathbf{Z}/n\mathbf{Z}$ for n small enough to be operated on in 64 bits

Author: Robert Bradshaw (2006-09-14)

Functions: is_one,$ \,$ is_unit,$ \,$ lift

is_one( )

Returns True if this is $ 1$ , otherwise False.

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.

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.

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

__copy__( )

__crt( )

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

__float__( )

Coerce self to a float.

sage: a = Mod(8943, 2^35)
sage: float(a)
8943.0

__index__( )

Needed so integers modulo $ n$ can be used as list indices.

sage: v = [1,2,3,4,5]
sage: v[Mod(3, 2^20)]
4

__int__( )

__invert__( )

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

__long__( )

__lshift__( )

sage: e = Mod(5, 2^31 - 1)
sage: e<<32
10
sage: e*2^32
10

__mod__( )

__rshift__( )

Divide self by $ 2^{ ext{right}}$ and take floor via bit shifting.

sage: e = Mod(8, 2^31 - 1)
sage: e >> 3
1
sage: int(e)/int(2^3)
1

_balanced_abs( )

This function returns $ x$ or $ -x$ , whichever has a positive representative in $ -n/2 < x \leq n/2$ .

Class: IntegerMod_to_IntegerMod

class IntegerMod_to_IntegerMod
Very fast IntegerMod to IntegerMod homomorphism.

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

_repr_type( )

Class: NativeIntStruct

class NativeIntStruct
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.

Functions: precompute_table

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

__reduce__( )

_get_table( )

See About this document... for information on suggesting changes.