Module: sage.rings.integer_mod_ring
Ring
of integers modulo
sage: R = Integers(97) sage: a = R(5) sage: a**100000000000000000000000000000000000000000000000000000000000000 61
This example illustrates the relation between
and
. In
particular, there is a canonical map to
, but not in the other
direction.
sage: r = Integers(7) sage: s = GF(7) sage: r.has_coerce_map_from(s) False sage: s.has_coerce_map_from(r) True sage: s(1) + r(1) 2 sage: parent(s(1) + r(1)) Finite Field of size 7 sage: parent(r(1) + s(1)) Finite Field of size 7
We list the elements of
sage: R = Integers(3) sage: list(R) [0, 1, 2]
Author Log:
Module-level Functions
[order=0]) |
Return the quotient ring
.
Input:
sage: IntegerModRing(15) Ring of integers modulo 15 sage: IntegerModRing(7) Ring of integers modulo 7 sage: IntegerModRing(-100) Ring of integers modulo 100
Note that you can also use Integers
, which is a synonym
for IntegerModRing
.
sage: Integers(18) Ring of integers modulo 18
[order=0]) |
Return the quotient ring
.
Input:
sage: IntegerModRing(15) Ring of integers modulo 15 sage: IntegerModRing(7) Ring of integers modulo 7 sage: IntegerModRing(-100) Ring of integers modulo 100
Note that you can also use Integers
, which is a synonym
for IntegerModRing
.
sage: Integers(18) Ring of integers modulo 18
[order=0]) |
Return the quotient ring
.
Input:
sage: IntegerModRing(15) Ring of integers modulo 15 sage: IntegerModRing(7) Ring of integers modulo 7 sage: IntegerModRing(-100) Ring of integers modulo 100
Note that you can also use Integers
, which is a synonym
for IntegerModRing
.
sage: Integers(18) Ring of integers modulo 18
v) |
Input: v - (list) a lift of elements of rings.integermod(n), for various coprime moduli n.
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, 'a')) False sage: is_IntegerModRing(10) False sage: is_IntegerModRing(ZZ) False
Class: IntegerModRing_generic
sage: R = IntegerModRing(97) sage: a = R(5) sage: a**(10^62) 61
self, order, [cache=None]) |
Create with the command IntegerModRing(order)
Input:
First we compute with integers modulo
.
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
.
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: cardinality,
characteristic,
coerce_map_from_impl,
factored_order,
field,
is_field,
is_finite,
is_integral_domain,
is_noetherian,
krull_dimension,
list_of_elements_of_multiplicative_group,
modulus,
multiplicative_generator,
multiplicative_group_is_cyclic,
multiplicative_subgroups,
order,
quadratic_nonresidue,
random_element,
square_roots_of_one,
unit_gens,
unit_group_exponent,
unit_group_order
self) |
sage: R = IntegerModRing(18) sage: FF = IntegerModRing(17) sage: FF.characteristic() 17 sage: R.characteristic() 18
self, S) |
sage: R = Integers(15) sage: f = R.coerce_map_from(Integers(450)); f Natural morphism: From: Ring of integers modulo 450 To: Ring of integers modulo 15 sage: f(-1) 14 sage: f = R.coerce_map_from(int); f Native morphism: From: Set of Python objects of type 'int' To: Ring of integers modulo 15 sage: f(-1r) 14 sage: f = R.coerce_map_from(ZZ); f Natural morphism: From: Integer Ring To: Ring of integers modulo 15 sage: f(-1) 14 sage: f = R.coerce_map_from(Integers(10)); print f None sage: f = R.coerce_map_from(QQ); print f None
self) |
sage: R = IntegerModRing(18) sage: FF = IntegerModRing(17) sage: R.factored_order() 2 * 3^2 sage: FF.factored_order() 17
self) |
If this ring is a field, return the corresponding field as a finite field, which may have extra functionality and structure. Otherwise, raise a ValueError.
sage: R = Integers(7); R Ring of integers modulo 7 sage: R.field() Finite Field of size 7 sage: R = Integers(9) sage: R.field() Traceback (most recent call last): ... ValueError: self must be a field
self) |
Return True precisely if the order is prime.
sage: R = IntegerModRing(18) sage: R.is_field() False sage: FF = IntegerModRing(17) sage: FF.is_field() True
self) |
Return True since Z/NZ is finite for all positive N.
sage: R = IntegerModRing(18) sage: R.is_finite() True
self) |
Return True if and only if the order of self is prime.
sage: Integers(389).is_integral_domain() True sage: Integers(389^2).is_integral_domain() False
self) |
sage: Integers(8).is_noetherian() True
self) |
sage: Integers(18).krull_dimension() 0
self) |
Return the polynomial
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
self) |
Return a generator for the multiplicative group of this ring, assuming the multiplicative group is cyclic.
Use the unit_gens function to obtain generators even in the non-cyclic case.
sage: R = Integers(7); R Ring of integers modulo 7 sage: R.multiplicative_generator() 3 sage: R = Integers(9) sage: R.multiplicative_generator() 2 sage: Integers(8).multiplicative_generator() Traceback (most recent call last): ... ValueError: multiplicative group of this ring is not cyclic sage: Integers(4).multiplicative_generator() 3 sage: Integers(25*3).multiplicative_generator() Traceback (most recent call last): ... ValueError: multiplicative group of this ring is not cyclic sage: Integers(25*3).unit_gens() [26, 52]
self) |
Return True if the multiplicative group of this field is cyclic. This is the case exactly when the order is less than 8 or a power of an odd prime.
sage: R = Integers(7); R Ring of integers modulo 7 sage: R.multiplicative_group_is_cyclic() True sage: R = Integers(9) sage: R.multiplicative_group_is_cyclic() True sage: Integers(8).multiplicative_group_is_cyclic() False sage: Integers(4).multiplicative_group_is_cyclic() True sage: Integers(25*3).multiplicative_group_is_cyclic() False
self) |
Return generators for each subgroup of
.
sage: Integers(5).multiplicative_subgroups() [[2], [4], [1]] sage: Integers(15).multiplicative_subgroups() [[11, 7], [11, 4], [11, 1], [1, 7], [1, 4], [1, 1]]
self) |
Return a quadratic non-residue in self.
sage: R = Integers(17) sage: R.quadratic_nonresidue() 3 sage: R(3).is_square() False
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() 2
self) |
Return all square roots of 1 in self, i.e., all solutions
to
.
Output:
sage: R = Integers(2^10) sage: [x for x in R if x^2 == 1] [1, 511, 513, 1023] sage: R.square_roots_of_one() (1, 511, 513, 1023)
sage: v = Integers(9*5).square_roots_of_one(); v (1, 19, 26, 44) sage: [x^2 for x in v] [1, 1, 1, 1] sage: v = Integers(9*5*8).square_roots_of_one(); v (1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359) sage: [x^2 for x in v] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
self) |
Returns generators for the unit group
.
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
(or
possibly two prime divisors for p=2).
Input: (none) Output:
sage: R = IntegerModRing(18) sage: R.unit_gens() [1, 11] sage: R = IntegerModRing(17) sage: R.unit_gens() [3] sage: IntegerModRing(next_prime(10^30)).unit_gens() [5]
self) |
sage: R = IntegerModRing(17) sage: R.unit_group_exponent() 16 sage: R = IntegerModRing(18) sage: R.unit_group_exponent() 6
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__,
__init__,
__iter__,
_coerce_impl,
_gap_init_,
_IntegerModRing_generic__unit_gens_primecase,
_IntegerModRing_generic__unit_gens_primepowercase,
_latex_,
_magma_init_,
_pari_order,
_precompute_table,
_pseudo_fraction_field,
_repr_
self, other) |
sage: F = GF(11) sage: F Finite Field of size 11 sage: R = IntegerModRing(11) sage: R == F False
self) |
sage: R = IntegerModRing(3) sage: for i in R: ... print i 0 1 2 sage: L = [i for i in R] sage: L[0].parent() Ring of integers modulo 3
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
to
.
sage: R._coerce_(2/3) Traceback (most recent call last): ... TypeError: no canonical coercion of x
We do not allow the coercion GF(p) -> Z/pZ, because in case of a canonical isomorphism, there is a coercion map in only one direction, i.e., to the object in the smaller category.
self) |
sage: R = Integers(12345678900) sage: R Ring of integers modulo 12345678900 sage: gap(R) (Integers mod 12345678900)
self, p, r) |
Find smallest generator for
.
self) |
sage: R = Integers(12345678900) sage: R Ring of integers modulo 12345678900 sage: magma(R) # optional Residue class ring of integers modulo 12345678900
self) |
If self is composite, we may still want to do divison by elements of self.
sage: Integers(15).fraction_field() Traceback (most recent call last): ... TypeError: self must be an integral domain. sage: Integers(15)._pseudo_fraction_field() Ring of integers modulo 15 sage: R.<x> = Integers(15)[] sage: (x+5)/2 8*x + 10
This should be very fast:
sage: R.<x> = Integers(next_prime(10^101)*next_prime(10^100))[] sage: x / R.base_ring()(2) 500000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000013365000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000401*x