Coverage for local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod

500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013365000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000401*x

"""

return self

@cached_method

def multiplicative_group_is_cyclic(self):

"""

Return ``True`` if the multiplicative group of this field is cyclic.

This is the case exactly when the order is less than 8, a power

of an odd prime, or twice a power of an odd prime.

EXAMPLES::

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

We test that :trac:`5250` is fixed::

sage: Integers(162).multiplicative_group_is_cyclic()

True

"""

n = self.order()

if n < 8:

return True

if n % 4 == 0:

return False # know n > 7, so n=4 case not a problem

if n % 4 == 2:

n = n // 2

return n.is_prime_power()

@cached_method

def multiplicative_generator(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.

EXAMPLES::

sage: R = Integers(7); R

Ring of integers modulo 7

sage: R.multiplicative_generator()

sage: R = Integers(9)

sage: R.multiplicative_generator()

sage: Integers(8).multiplicative_generator()

Traceback (most recent call last):

...

ValueError: multiplicative group of this ring is not cyclic

sage: Integers(4).multiplicative_generator()

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)

sage: Integers(162).unit_gens()

(83,)

"""

try:

return self.__mult_gen

except AttributeError:

if self.is_field():

a = self(self.field().multiplicative_generator())

self.__mult_gen = a

return a

if self.multiplicative_group_is_cyclic():

v = self.unit_gens()

if len(v) != 1:

raise ArithmeticError

return v[0]

raise ValueError("multiplicative group of this ring is not cyclic")

def quadratic_nonresidue(self):

"""

Return a quadratic non-residue in ``self``.

EXAMPLES::

sage: R = Integers(17)

sage: R.quadratic_nonresidue()

sage: R(3).is_square()

False

"""

try:

return self._nonresidue

except AttributeError:

for a in self:

if not a.is_square():

self._nonresidue = a

return a

def square_roots_of_one(self):

"""

Return all square roots of 1 in self, i.e., all solutions to

`x^2 - 1 = 0`.

OUTPUT:

The square roots of 1 in ``self`` as a tuple.

EXAMPLES::

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]

"""

try:

return self.__square_roots_of_one

except AttributeError:

pass

n = self.__order

if n.is_prime_power():

if n % 2 == 0:

# power of 2

if n == 2:

v = [self(1)]

elif n == 4:

v = [self(1), self(3)]

else: # n >= 8

half_ord = n//2

v = [self(1), self(-1), self(half_ord-1), self(half_ord+1)]

else:

v = [self(1), self(-1)]

else:

# Reduce to the prime power case.

F = self.factored_order()

vmod = []

moduli = []

for p, e in F:

k = p**e

R = IntegerModRing(p**e)

w = [self(x) for x in R.square_roots_of_one()]

vmod.append(w)

moduli.append(k)

# Now combine in all possible ways using the CRT

basis = CRT_basis(moduli)

from sage.misc.mrange import cartesian_product_iterator

v = []

for x in cartesian_product_iterator(vmod):

# x is a specific choice of roots modulo each prime power divisor

a = sum([basis[i]*x[i] for i in range(len(x))])

v.append(a)

#end for

#end if

v.sort()

v = tuple(v)

self.__square_roots_of_one = v

return v

@cached_method

def factored_order(self):

"""

EXAMPLES::

sage: R = IntegerModRing(18)

sage: FF = IntegerModRing(17)

sage: R.factored_order()

2 * 3^2

sage: FF.factored_order()

"""

return factor(self.__order, int_=(self.__order < 2**31))

def factored_unit_order(self):

"""

Return a list of :class:`Factorization` objects, each the factorization

of the order of the units in a `\ZZ / p^n \ZZ` component of this group

(using the Chinese Remainder Theorem).

EXAMPLES::

sage: R = Integers(8*9*25*17*29)

sage: R.factored_unit_order()

[2^2, 2 * 3, 2^2 * 5, 2^4, 2^2 * 7]

"""

ans = []

from sage.structure.factorization import Factorization

for p, e in self.factored_order():

ans.append(Factorization([(p,e-1)]) * factor(p-1, int_=(self.__order < 2**31)))

return ans

def characteristic(self):

"""

EXAMPLES::

sage: R = IntegerModRing(18)

sage: FF = IntegerModRing(17)

sage: FF.characteristic()

sage: R.characteristic()

"""

return self.__order

def _repr_(self):

"""

String representation.

EXAMPLES::

sage: Zmod(87)

Ring of integers modulo 87

"""

return "Ring of integers modulo {}".format(self.__order)

def _latex_(self):

r"""

Latex representation.

EXAMPLES::

sage: latex(Zmod(87))

\ZZ/87\ZZ

"""

return "\\ZZ/{}\\ZZ".format(self.__order)

def modulus(self):

r"""

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

.. NOTE::

This function exists for consistency with the finite-field

modulus function.

EXAMPLES::

sage: R = IntegerModRing(18)

sage: R.modulus()

x + 17

sage: R = IntegerModRing(17)

sage: R.modulus()

x + 16

"""

try:

return self.__modulus

except AttributeError:

x = self['x'].gen()

self.__modulus = x - 1

return self.__modulus

def order(self):

"""

Return the order of this ring.

EXAMPLES::

sage: Zmod(87).order()

"""

return self.__order

def cardinality(self):

"""

Return the cardinality of this ring.

EXAMPLES::

sage: Zmod(87).cardinality()

"""

return self.order()

def _pari_order(self):

"""

Return the pari integer representing the order of this ring.

EXAMPLES::

sage: Zmod(87)._pari_order()

"""

try:

return self.__pari_order

except AttributeError:

self.__pari_order = pari(self.order())

return self.__pari_order

def _element_constructor_(self, x):

"""

TESTS::

sage: K2 = GF(2)

sage: K3 = GF(3)

sage: K8 = GF(8,'a')

sage: K8(5) # indirect doctest

sage: K8('a+1')

a + 1

sage: K8(K2(1))

The following test refers to :trac:`6468`::

sage: class foo_parent(Parent):

....: pass

sage: class foo(RingElement):

....: def lift(self):

....: raise PariError

sage: P = foo_parent()

sage: F = foo(P)

sage: GF(2)(F)

Traceback (most recent call last):

...

TypeError: error coercing to finite field

The following test refers to :trac:`8970`::

sage: R = Zmod(13); a = R(2)

sage: a == R(gap(a))

True

libgap interface (:trac:`23714`)::

sage: a = libgap.eval("Z(13)^2")

sage: a.sage()

sage: libgap(a.sage()) == a

True

"""

try:

return integer_mod.IntegerMod(self, x)

except (NotImplementedError, PariError):

raise TypeError("error coercing to finite field")

except TypeError:

if sage.interfaces.gap.is_GapElement(x):

from sage.interfaces.gap import intmod_gap_to_sage

y = intmod_gap_to_sage(x)

return integer_mod.IntegerMod(self, y)

raise # Continue up with the original TypeError

def __iter__(self):

"""

EXAMPLES::

sage: R = IntegerModRing(3)

sage: for i in R:

....: print(i)

sage: L = [i for i in R]

sage: L[0].parent()

Ring of integers modulo 3

"""

i = 0

order = int(self.__order)

while i < order:

yield self(i)

i = i + 1

def _coerce_map_from_(self, S):

"""

EXAMPLES::

sage: R = Integers(15)

sage: f = R.coerce_map_from(Integers(450)); f # indirect doctest

Natural morphism:

From: Ring of integers modulo 450

To: Ring of integers modulo 15

sage: f(-1)

sage: f = R.coerce_map_from(int); f

Native morphism:

From: Set of Python objects of class 'int'

To: Ring of integers modulo 15

sage: f(-1r)

sage: f = R.coerce_map_from(ZZ); f

Natural morphism:

From: Integer Ring

To: Ring of integers modulo 15

sage: f(-1)

sage: f = R.coerce_map_from(Integers(10)); print(f)

None

sage: f = R.coerce_map_from(QQ); print(f)

None

sage: R = IntegerModRing(17)

sage: a = R(3)

sage: b = R._coerce_(3)

sage: b

sage: a==b

True

This is allowed::

sage: R(2/3)

But this is not, since there is no (canonical or not!) ring

homomorphism from `\QQ` to `\GF{17}`.

sage: R._coerce_(2/3)

Traceback (most recent call last):

...

TypeError: no canonical coercion from Rational Field to Ring of integers modulo 17

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.

"""

if S is int:

return integer_mod.Int_to_IntegerMod(self)

elif S is integer_ring.ZZ:

return integer_mod.Integer_to_IntegerMod(self)

elif isinstance(S, IntegerModRing_generic):

if isinstance(S, ring.Field):

return None

try:

return integer_mod.IntegerMod_to_IntegerMod(S, self)

except TypeError:

pass

to_ZZ = integer_ring.ZZ._internal_coerce_map_from(S)

if to_ZZ is not None:

return integer_mod.Integer_to_IntegerMod(self) * to_ZZ

def _convert_map_from_(self, other):

"""

Conversion from p-adic fields.

EXAMPLES::

sage: Zmod(81).convert_map_from(Qp(3))

Reduction morphism:

From: 3-adic Field with capped relative precision 20

To: Ring of integers modulo 81

"""

from sage.rings.padics.padic_generic import pAdicGeneric, ResidueReductionMap

if isinstance(other, pAdicGeneric) and other.degree() == 1:

p = other.prime()

N = self.cardinality()

n = N.exact_log(p)

if p**n == N:

return ResidueReductionMap._create_(other, self)

def __richcmp__(self, other, op):

"""

EXAMPLES::

sage: Z11 = IntegerModRing(11); Z11

Ring of integers modulo 11

sage: Z12 = IntegerModRing(12); Z12

Ring of integers modulo 12

sage: Z13 = IntegerModRing(13); Z13

Ring of integers modulo 13

sage: F = GF(11); F

Finite Field of size 11

sage: Z11 == Z11, Z11 == Z12, Z11 == Z13, Z11 == F

(True, False, False, False)

In :trac:`15229`, the following was implemented::

sage: R1 = IntegerModRing(5)

sage: R2 = IntegerModRing(5, is_field=True)

sage: R1 is R2 # used to return False

True

sage: R2 == GF(5)

False

"""

# We want that GF(p) and IntegerModRing(p) evaluate unequal.

# However, we can not just compare the types, since the

# choice of a different category also changes the type.

# But if we go to the base class, we avoid the influence

# of the category.

try:

c = bool(other.__class__.__base__ != self.__class__.__base__)

except AttributeError: # __base__ does not always exists

c = bool(type(other) != type(self))

if c:

return NotImplemented

return richcmp(self.__order, other.__order, op)

def unit_gens(self, **kwds):

r"""

Returns generators for the unit group `(\ZZ/N\ZZ)^*`.

We compute the list of generators using a deterministic algorithm, so

the generators list will always be the same. For each odd prime divisor

of `N` there will be exactly one corresponding generator; if `N` is

even there will be 0, 1 or 2 generators according to whether 2 divides

`N` to order 1, 2 or `\geq 3`.

OUTPUT:

A tuple containing the units of ``self``.

EXAMPLES::

sage: R = IntegerModRing(18)

sage: R.unit_gens()

(11,)

sage: R = IntegerModRing(17)

sage: R.unit_gens()

(3,)

sage: IntegerModRing(next_prime(10^30)).unit_gens()

(5,)

The choice of generators is affected by the optional keyword

``algorithm``; this can be ``'sage'`` (default) or ``'pari'``.

See :meth:`unit_group` for details.

sage: A = Zmod(55)

sage: A.unit_gens(algorithm='sage')

(12, 46)

sage: A.unit_gens(algorithm='pari')

(2, 21)

TESTS::

sage: IntegerModRing(2).unit_gens()

()

sage: IntegerModRing(4).unit_gens()

(3,)

sage: IntegerModRing(8).unit_gens()

(7, 5)

"""

return self.unit_group(**kwds).gens_values()

def unit_group_exponent(self):

"""

EXAMPLES::

sage: R = IntegerModRing(17)

sage: R.unit_group_exponent()

sage: R = IntegerModRing(18)

sage: R.unit_group_exponent()

"""

return self.unit_group().exponent()

def 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

"""

return self.unit_group().order()

@cached_method

def unit_group(self, algorithm='sage'):

r"""

Return the unit group of ``self``.

INPUT:

- ``self`` -- the ring `\ZZ/n\ZZ` for a positive integer `n`

- ``algorithm`` -- either ``'sage'`` (default) or ``'pari'``

OUTPUT:

The unit group of ``self``. This is a finite Abelian group

equipped with a distinguished set of generators, which is

computed using a deterministic algorithm depending on the

``algorithm`` parameter.

- If ``algorithm == 'sage'``, the generators correspond to the

prime factors `p \mid n` (one generator for each odd `p`;

the number of generators for `p = 2` is 0, 1 or 2 depending

on the order to which 2 divides `n`).

- If ``algorithm == 'pari'``, the generators are chosen such

that their orders form a decreasing sequence with respect to

divisibility.

EXAMPLES:

The output of the algorithms ``'sage'`` and ``'pari'`` can

differ in various ways. In the following example, the same

cyclic factors are computed, but in a different order::

sage: A = Zmod(15)

sage: G = A.unit_group(); G

Multiplicative Abelian group isomorphic to C2 x C4

sage: G.gens_values()

(11, 7)

sage: H = A.unit_group(algorithm='pari'); H

Multiplicative Abelian group isomorphic to C4 x C2

sage: H.gens_values()

(7, 11)

Here are two examples where the cyclic factors are isomorphic,

but are ordered differently and have different generators::

sage: A = Zmod(40)

sage: G = A.unit_group(); G

Multiplicative Abelian group isomorphic to C2 x C2 x C4

sage: G.gens_values()

(31, 21, 17)

sage: H = A.unit_group(algorithm='pari'); H

Multiplicative Abelian group isomorphic to C4 x C2 x C2

sage: H.gens_values()

(17, 31, 21)

sage: A = Zmod(192)

sage: G = A.unit_group(); G

Multiplicative Abelian group isomorphic to C2 x C16 x C2

sage: G.gens_values()

(127, 133, 65)

sage: H = A.unit_group(algorithm='pari'); H

Multiplicative Abelian group isomorphic to C16 x C2 x C2

sage: H.gens_values()

(133, 127, 65)

In the following examples, the cyclic factors are not even

isomorphic::

sage: A = Zmod(319)

sage: A.unit_group()

Multiplicative Abelian group isomorphic to C10 x C28

sage: A.unit_group(algorithm='pari')

Multiplicative Abelian group isomorphic to C140 x C2

sage: A = Zmod(30.factorial())

sage: A.unit_group()

Multiplicative Abelian group isomorphic to C2 x C16777216 x C3188646 x C62500 x C2058 x C110 x C156 x C16 x C18 x C22 x C28

sage: A.unit_group(algorithm='pari')

Multiplicative Abelian group isomorphic to C20499647385305088000000 x C55440 x C12 x C12 x C4 x C2 x C2 x C2 x C2 x C2 x C2

TESTS:

We test the cases where the unit group is trivial::

sage: A = Zmod(1)

sage: A.unit_group()

Trivial Abelian group

sage: A.unit_group(algorithm='pari')

Trivial Abelian group

sage: A = Zmod(2)

sage: A.unit_group()

Trivial Abelian group

sage: A.unit_group(algorithm='pari')

Trivial Abelian group

sage: Zmod(3).unit_group(algorithm='bogus')

Traceback (most recent call last):

...

ValueError: unknown algorithm 'bogus' for computing the unit group

"""

from sage.groups.abelian_gps.values import AbelianGroupWithValues

if algorithm == 'sage':

n = self.order()

gens = []

orders = []

for p, r in self.factored_order():

m = n/(p**r)

for g, o in _unit_gens_primepowercase(p, r):

x = g.crt(integer_mod.Mod(1, m))

gens.append(x)

orders.append(o)

elif algorithm == 'pari':

_, orders, gens = self.order().__pari__().znstar()

gens = map(self, gens)

orders = map(integer.Integer, orders)

else:

raise ValueError('unknown algorithm %r for computing the unit group' % algorithm)

return AbelianGroupWithValues(gens, orders, values_group=self)

def random_element(self, bound=None):

"""

Return a random element of this ring.

INPUT:

- ``bound``, a positive integer or ``None`` (the default). Is given,

return the coercion of an integer in the interval

``[-bound, bound]`` into this ring.

EXAMPLES::

sage: R = IntegerModRing(18)

sage: R.random_element()

We test ``bound``-option::

sage: R.random_element(2) in [R(16), R(17), R(0), R(1), R(2)]

True

"""

if bound is not None:

return ring.CommutativeRing.random_element(self, bound)

a = random.randint(0,self.order()-1)

return self(a)

#######################################################

# Suppose for interfaces

#######################################################

def _gap_init_(self):

"""

EXAMPLES::

sage: R = Integers(12345678900)

sage: R

Ring of integers modulo 12345678900

sage: gap(R) # indirect doctest

(Integers mod 12345678900)

"""

return 'ZmodnZ({})'.format(self.order())

def _magma_init_(self, magma):

"""

EXAMPLES::

sage: R = Integers(12345678900)

sage: R

Ring of integers modulo 12345678900

sage: magma(R) # indirect doctest, optional - magma

Residue class ring of integers modulo 12345678900

"""

return 'Integers({})'.format(self.order())

def degree(self):

"""

Return 1.

EXAMPLES::

sage: R = Integers(12345678900)

sage: R.degree()

"""

return integer.Integer(1)

Zmod = IntegerModRing

Integers = IntegerModRing

# Register unpickling methods for backward compatibility.

from sage.structure.sage_object import register_unpickle_override

register_unpickle_override('sage.rings.integer_mod_ring', 'IntegerModRing_generic', IntegerModRing_generic)

def crt(v):

"""

INPUT:

- ``v`` -- (list) a lift of elements of ``rings.IntegerMod(n)``, for

various coprime moduli ``n``

EXAMPLES::

sage: from sage.rings.finite_rings.integer_mod_ring import crt

sage: crt([mod(3, 8),mod(1,19),mod(7, 15)])

1027

"""

if len(v) == 0:

return IntegerModRing(1)(1)

x = v[0]

for i in range(1,len(v)):

x = x.crt(v[i])

return x

Coverage for local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod_ring.py : 72%

323 statements 231 run 92 missing 0 excluded