12.3 Ring $ \mathbf{Z}/n\mathbf{Z}$ of integers modulo $ n$

Module: sage.rings.integer_mod_ring

sage: R = Integers(97)
sage: a = R(5)
sage: a**100000000000000000000000000000000000000000000000000000000000000
61

Author Log:

Module-level Functions

IntegerModRing( [order=True], [check_prime=0])

INPUT:
    order -- integer (default: 0)
    check_prime -- bool (default: True); if False do not test for
                   primality of the order in constructing the
                   residue class ring (thus always constructing
                   the generic integer_mod_ring that doesn't
                   have special field functionality and implementation).
                   Do this if the modulus is huge (thousands of digits).

sage: IntegerModRing(15)
Ring of integers modulo 15

The following example illustrates the check_prime option. Without it, just defining R would take a very long time.

sage: n = 5*2^23473+1
sage: len(str(n))
7067
sage: R = IntegerModRing(n, check_prime=False)
sage: type(R)
<class 'sage.rings.integer_mod_ring.IntegerModRing_generic'>

Note that you can also user Integers, which is a synonym for IntegerModRing.

sage: Integers(18)
Ring of integers modulo 18

Integers( [order=True], [check_prime=0])

INPUT:
    order -- integer (default: 0)
    check_prime -- bool (default: True); if False do not test for
                   primality of the order in constructing the
                   residue class ring (thus always constructing
                   the generic integer_mod_ring that doesn't
                   have special field functionality and implementation).
                   Do this if the modulus is huge (thousands of digits).

sage: IntegerModRing(15)
Ring of integers modulo 15

The following example illustrates the check_prime option. Without it, just defining R would take a very long time.

sage: n = 5*2^23473+1
sage: len(str(n))
7067
sage: R = IntegerModRing(n, check_prime=False)
sage: type(R)
<class 'sage.rings.integer_mod_ring.IntegerModRing_generic'>

Note that you can also user Integers, which is a synonym for IntegerModRing.

sage: Integers(18)
Ring of integers modulo 18

Zmod( [order=True], [check_prime=0])

INPUT:
    order -- integer (default: 0)
    check_prime -- bool (default: True); if False do not test for
                   primality of the order in constructing the
                   residue class ring (thus always constructing
                   the generic integer_mod_ring that doesn't
                   have special field functionality and implementation).
                   Do this if the modulus is huge (thousands of digits).

sage: IntegerModRing(15)
Ring of integers modulo 15

The following example illustrates the check_prime option. Without it, just defining R would take a very long time.

sage: n = 5*2^23473+1
sage: len(str(n))
7067
sage: R = IntegerModRing(n, check_prime=False)
sage: type(R)
<class 'sage.rings.integer_mod_ring.IntegerModRing_generic'>

Note that you can also user Integers, which is a synonym for IntegerModRing.

sage: Integers(18)
Ring of integers modulo 18

crt( v)

INPUT: v -- (list) a lift of elements of rings.IntegerMod(n), for
             various coprime moduli n.

is_IntegerModRing( x)

Return True if x is an integer modulo ring.

sage: R = IntegerModRing(17)
sage: is_IntegerModRing(R)
True
sage: is_IntegerModRing(GF(13))
True
sage: is_IntegerModRing(GF(4))
False
sage: is_IntegerModRing(10)
False
sage: is_IntegerModRing(ZZ)
False

Class: IntegerModRing_field

class IntegerModRing_field
IntegerModRing_field( self, order)

Class: IntegerModRing_generic

class IntegerModRing_generic
The ring of integers modulo N, e.g., when N is prime this is a prime finite field.

sage: R = IntegerModRing(97)
sage: a = R(5)
sage: a**(10^62)
61
IntegerModRing_generic( self, order)

Create with the command IntegerModRing(order)

INPUT:
    order -- an integer > 1

OUTPUT:
    IntegerModRing -- the ring of integers modulo N.

First we compute with integers modulo $ 17$ .

sage: FF = IntegerModRing(17)
sage: FF
Ring of integers modulo 17
sage: FF.is_field()
True
sage: FF.characteristic()
17
sage: FF.order()
17
sage: gens = FF.unit_gens()
sage: a = gens[0]
sage: a
3
sage: a.is_square()
False
sage: def pow(i): return a**i
sage: [pow(i) for i in range(16)]
[1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6]

Next we compute with the integers modulo $ 16$ .

sage: Z16 = IntegerModRing(16)
sage: Z16.is_field()
False
sage: Z16.order()
16
sage: Z16.characteristic() 
16
sage: gens = Z16.unit_gens()
sage: gens
[15, 5]
sage: a = gens[0]
sage: b = gens[1]
sage: def powa(i): return a**i
sage: def powb(i): return b**i
sage: gp_exp = FF.unit_group_exponent()
sage: gp_exp
16
sage: [powa(i) for i in range(15)]
[1, 15, 1, 15, 1, 15, 1, 15, 1, 15, 1, 15, 1, 15, 1]
sage: [powb(i) for i in range(15)]
[1, 5, 9, 13, 1, 5, 9, 13, 1, 5, 9, 13, 1, 5, 9]
sage: a.multiplicative_order()
2
sage: b.multiplicative_order()
4

Saving and loading:

sage: R = Integers(100000)
sage: loads(R.dumps()) == R
True

Functions: characteristic,$  $ factored_order,$  $ is_field,$  $ is_finite,$  $ modulus,$  $ order,$  $ random_element,$  $ unit_gens,$  $ unit_group_exponent,$  $ unit_group_order

characteristic( self)

sage: R = IntegerModRing(18)
sage: FF = IntegerModRing(17)
sage: FF.characteristic()
17
sage: R.characteristic()
18

factored_order( self)

sage: R = IntegerModRing(18)
sage: FF = IntegerModRing(17)
sage: R.factored_order()
2 * 3^2
sage: FF.factored_order()
17

is_field( self)

sage: R = IntegerModRing(18)
sage: R.is_field()
False
sage: FF = IntegerModRing(17)
sage: FF.is_field()
True

is_finite( self)

sage: R = IntegerModRing(18)
sage: R.is_finite()
True

modulus( self)

Return the polynomial $ x - 1$ over this ring.

Note: This function exists for consistency with the finite-field modulus function.

sage: R = IntegerModRing(18)
sage: R.modulus()
x + 17
sage: R = IntegerModRing(17)
sage: R.modulus()
x + 16

random_element( self, [bound=None])

Return a random element of this ring.

If bound is not None, return the coercion of an integer in the interval [-bound, bound] into this ring.

sage: R = IntegerModRing(18)
sage: R.random_element()
15

unit_gens( self)

Returns generators for the unit group $ (\mathbf{Z}/N\mathbf{Z})^*$ .

We compute the list of generators using a deterministic algorithm, so the generators list will always be the same. Each generator corresponds to a prime divisor of $ N$ (or possibly two prime divisors for p=2).

INPUT: (none)
OUTPUT:
    list -- a list of elements of self

sage: R = IntegerModRing(18)
sage: R.unit_gens()
[1, 11]
sage: R = IntegerModRing(17)
sage: R.unit_gens()
[3]

unit_group_exponent( self)

sage: R = IntegerModRing(17)
sage: R.unit_group_exponent()
16
sage: R = IntegerModRing(18)
sage: R.unit_group_exponent()
6

unit_group_order( self)

Return the order of the unit group of this residue class ring.

EXAMPLES;

sage: R = Integers(500)
sage: R.unit_group_order()
200

Special Functions: __call__,$  $ __cmp__,$  $ _coerce_,$  $ _gap_init_,$  $ _IntegerModRing_generic__unit_gens_primecase,$  $ _IntegerModRing_generic__unit_gens_primepowercase,$  $ _magma_init_,$  $ _repr_

__cmp__( self, other)

sage: F = GF(11)
sage: F
Finite Field of size 11
sage: R = IntegerModRing(11)
sage: R == F
True

_coerce_( self, x)

Canonical coercion.

sage: R = IntegerModRing(17)
sage: a = R(3)
sage: b = R._coerce_(3)
sage: b
3
sage: a==b
True

This is allowed:

sage: R(2/3)
12

But this is not, since there is no (canonical or not!) ring homomorphism from $ \mathbf{Q}$ to $ \GF (17)$ .

sage: R._coerce_(2/3)
Traceback (most recent call last):
...
TypeError: no canonical coercion of 2/3 into Ring of integers modulo 17

_gap_init_( self)

sage: R = Integers(12345678900)
sage: R
Ring of integers modulo 12345678900
sage: gap(R)
(Integers mod 12345678900)

_IntegerModRing_generic__unit_gens_primepowercase( self, p, r)

Find smallest generator for $ (\mathbf{Z}/p^r\mathbf{Z})^*$ .

_magma_init_( self)

sage: R = Integers(12345678900)
sage: R
Ring of integers modulo 12345678900
sage: magma(R)                                          # optional
Residue class ring of integers modulo 12345678900

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