Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" 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
TESTS::
sage: R = Integers(101^3) sage: a = R(824362); b = R(205942) sage: a * b 851127
sage: type(IntegerModRing(2^31-1).an_element()) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'> sage: type(IntegerModRing(2^31).an_element()) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> """
#***************************************************************************** # Copyright (C) 2006 Robert Bradshaw <robertwb@math.washington.edu> # 2006 William Stein <wstein@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function, division, absolute_import
from cysignals.signals cimport sig_on, sig_off
from cpython.int cimport * from cpython.list cimport * from cpython.ref cimport *
from libc.math cimport log, ceil
from sage.libs.gmp.all cimport *
import operator
cdef bint use_32bit_type(int_fast64_t modulus):
from sage.arith.long cimport integer_check_long, integer_check_long_py, ERR_OVERFLOW
import sage.rings.rational as rational from sage.libs.pari.all import pari, PariError import sage.rings.integer_ring as integer_ring
import sage.interfaces.all
import sage.rings.integer import sage.rings.integer_ring cimport sage.rings.integer from sage.rings.integer cimport Integer
import sage.structure.element cimport sage.structure.element coerce_binop = sage.structure.element.coerce_binop from sage.structure.element cimport RingElement, ModuleElement, Element from sage.categories.morphism cimport Morphism from sage.categories.map cimport Map
from sage.structure.sage_object import register_unpickle_override from sage.misc.superseded import deprecated_function_alias
from sage.structure.parent cimport Parent
cdef Integer one_Z = Integer(1)
def Mod(n, m, parent=None): """ 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
You can also use the lowercase version::
sage: mod(12,5) 2
Illustrates that :trac:`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 """ # when m is zero, then ZZ/0ZZ is isomorphic to ZZ
# m is non-zero, so return n mod m cdef IntegerMod_abstract x
mod = Mod
register_unpickle_override('sage.rings.integer_mod', 'Mod', Mod) register_unpickle_override('sage.rings.integer_mod', 'mod', mod)
def IntegerMod(parent, value): """ 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) <type 'list'> sage: IntegerMod(R, 42) 42 sage: IntegerMod(R, 142) 42 sage: IntegerMod(R, 10^100 + 42) 42 sage: IntegerMod(R, -9158) 42 """
cdef int err
# Try to return an element from the precomputed table
def is_IntegerMod(x): """ 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) False sage: is_IntegerMod(Mod(5,10)) True """
cdef inline inverse_or_None(x):
cdef 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. """ def __cinit__(self):
def __init__(self, m):
def __repr__(self):
def __reduce__(self): """ TESTS::
sage: from sage.rings.finite_rings.integer_mod import NativeIntStruct sage: M = NativeIntStruct(12345); M NativeIntStruct(12345) sage: loads(dumps(M)) NativeIntStruct(12345) """
def precompute_table(self, parent): """ 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]
This is used by the :class:`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
Check that the inverse of 0 modulo 1 works, see :trac:`13639`::
sage: R = IntegerModRing_generic(1, cache=True) # indirect doctest sage: R(0)^-1 is R(0) True
TESTS::
sage: R = IntegerModRing(10^50) sage: M = NativeIntStruct(R.order()) sage: M.precompute_table(R) Traceback (most recent call last): ... OverflowError: precompute_table() is only supported for small moduli """
# Verify that the modulus m fits in a Py_ssize_t
# Special case for integers modulo 1 else:
# For unpickling makeNativeIntStruct = NativeIntStruct register_unpickle_override('sage.rings.integer_mod', 'makeNativeIntStruct', NativeIntStruct)
cdef class IntegerMod_abstract(FiniteRingElement):
def __init__(self, parent, value=None): """ EXAMPLES::
sage: a = Mod(10, 30^10); a 10 sage: type(a) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: loads(a.dumps()) == a True """
cdef Integer z
else:
cdef IntegerMod_abstract _new_c_fast(self, unsigned long value):
cdef _new_c_from_long(self, long value):
cdef void set_from_mpz(self, mpz_t value): raise NotImplementedError("must be defined in child class")
cdef void set_from_long(self, long value): raise NotImplementedError("must be defined in child class")
cdef void set_from_ulong_fast(self, unsigned long value): """ Set ``self`` to the value in ``value`` where ``value`` is assumed to be less than the modulus """ raise NotImplementedError("must be defined in child class")
def __abs__(self): """ Raise an error message, since ``abs(x)`` makes no sense when ``x`` is an integer modulo `n`.
EXAMPLES::
sage: abs(Mod(2,3)) Traceback (most recent call last): ... ArithmeticError: absolute valued not defined on integers modulo n. """
def __reduce__(IntegerMod_abstract self): """ EXAMPLES::
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 """
def _im_gens_(self, codomain, im_gens): """ Return the image of ``self`` under the map that sends the generators of the parent to ``im_gens``.
EXAMPLES::
sage: a = Mod(7, 10) sage: R = ZZ.quotient(5) sage: a._im_gens_(R, (R(1),)) 2 """
def __mod__(self, modulus): """ Coerce this element to the ring `Z/(modulus)`.
If the new ``modulus`` does not divide the current modulus, an ``ArithmeticError`` is raised.
EXAMPLES::
sage: a = Mod(14, 35) sage: a % 5 4 sage: parent(a % 5) Ring of integers modulo 5 sage: a % 350 Traceback (most recent call last): ... ArithmeticError: reduction modulo 350 not defined sage: a % 35 14 sage: int(1) % a Traceback (most recent call last): ... TypeError: unsupported operand type(s) for %: 'int' and 'sage.rings.finite_rings.integer_mod.IntegerMod_int' """ # something % Mod(x,y) makes no sense
def is_nilpotent(self): r""" Return ``True`` if ``self`` is nilpotent, i.e., some power of ``self`` is zero.
EXAMPLES::
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 \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 :-). """ return True
################################################################# # Interfaces ################################################################# def _pari_init_(self): return 'Mod(%s,%s)'%(str(self), self.__modulus.sageInteger)
def __pari__(self):
def _gap_init_(self): r""" Return string representation of corresponding GAP object.
EXAMPLES::
sage: a = Mod(2,19) sage: gap(a) Z(19) sage: gap(Mod(3, next_prime(10000))) Z(10007)^6190 sage: gap(Mod(3, next_prime(100000))) ZmodpZObj( 3, 100003 ) sage: gap(Mod(4, 48)) ZmodnZObj( 4, 48 ) """
def _magma_init_(self, magma): """ Coercion to Magma.
EXAMPLES::
sage: a = Integers(15)(4) sage: b = magma(a) # optional - magma sage: b.Type() # optional - magma RngIntResElt sage: b^2 # optional - magma 1 """ return '%s!%s'%(self.parent()._magma_init_(magma), self)
def _axiom_init_(self): """ Return a string representation of the corresponding to (Pan)Axiom object.
EXAMPLES::
sage: a = Integers(15)(4) sage: a._axiom_init_() '4 :: IntegerMod(15)'
sage: aa = axiom(a); aa #optional - axiom 4 sage: aa.type() #optional - axiom IntegerMod 15
sage: aa = fricas(a); aa #optional - fricas 4 sage: aa.typeOf() #optional - fricas IntegerMod(15)
"""
_fricas_init_ = _axiom_init_
def _sage_input_(self, sib, coerced): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: K = GF(7) sage: sage_input(K(5), verify=True) # Verified GF(7)(5) sage: sage_input(K(5) * polygen(K), verify=True) # Verified R.<x> = GF(7)[] 5*x sage: from sage.misc.sage_input import SageInputBuilder sage: K(5)._sage_input_(SageInputBuilder(), False) {call: {call: {atomic:GF}({atomic:7})}({atomic:5})} sage: K(5)._sage_input_(SageInputBuilder(), True) {atomic:5} """ else:
def log(self, b=None, logarithm_exists=False): r""" 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``.
- ``logarithm_exists`` - a boolean (default ``False``). If ``True`` it assumes that the logarithm exists in order to speed up the computation, the code might end up in an infinite loop if this is set to ``True`` but the logarithm does not exist.
OUTPUT: Integer `x` such that `b^x = a`, if this exists; a ValueError otherwise.
.. NOTE::
If the modulus is prime and b is a generator, this calls Pari's ``znlog`` function, which is rather fast. If not, it falls back on the generic discrete log implementation in :meth:`sage.groups.generic.discrete_log`.
EXAMPLES::
sage: r = Integers(125) sage: b = r.multiplicative_generator()^3 sage: a = b^17 sage: a.log(b) 17 sage: a.log() 51
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.
::
sage: Mod(3, 7).log(Mod(2, 7)) Traceback (most recent call last): ... ValueError: No discrete log 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
TESTS:
We check that :trac:`9205` is fixed::
sage: Mod(5,9).log(Mod(2, 9)) 5
We test against a bug (side effect on PARI) fixed in :trac:`9438`::
sage: R.<a, b> = QQ[] sage: pari(b) b sage: GF(7)(5).log() 5 sage: pari(b) b
We test that :trac:`23927` is fixed::
sage: x = mod(48475563673907791151, 10^20 + 763)^2 sage: e = 25248843418589594761 sage: (x^e).log(x)==e True
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 """
else: raise ValueError("logarithm with base %s is not defined since it is not a unit modulo %s"%(b, b.modulus()))
except PariError as msg: raise RuntimeError("%s\nPARI failed to compute discrete log (perhaps base is not a generator or is too large)" % msg) else: raise ValueError("No discrete log of %s found to base %s modulo %s"%(self, b, self.modulus()))
else: # fall back on slower native implementation
def generalised_log(self): r""" Return integers `[n_1, \ldots, n_d]` such that
.. MATH::
\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 [1, 3, 1] sage: prod([Zmod(1568).unit_gens()[i] ** v[i] for i in [0..2]]) 3
.. SEEALSO::
The method :meth:`log`.
.. warning::
The output is given relative to the set of generators obtained by passing ``algorithm='sage'`` to the method :meth:`~sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic.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.
""" raise ZeroDivisionError else:
def modulus(IntegerMod_abstract self): """ EXAMPLES::
sage: Mod(3,17).modulus() 17 """
def charpoly(self, var='x'): """ 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
AUTHORS:
- Craig Citro """
def minpoly(self, var='x'): """ Returns the minimal polynomial of this element.
EXAMPLES: sage: GF(241, 'a')(1).minpoly() x + 240 """
def minimal_polynomial(self, var='x'): """ Returns the minimal polynomial of this element.
EXAMPLES: sage: GF(241, 'a')(1).minimal_polynomial(var = 'z') z + 240 """
def polynomial(self, var='x'): """ 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()) <type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'> """
def norm(self): """ 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
AUTHORS:
- Craig Citro """
def trace(self): """ 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
AUTHORS:
- Craig Citro """
def lift_centered(self): r""" 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 """ else:
centerlift = deprecated_function_alias(15804,lift_centered)
cpdef bint is_one(self): raise NotImplementedError
cpdef bint is_unit(self): raise NotImplementedError
def is_square(self): r""" EXAMPLES::
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
sage: for p,q,r in cartesian_product_iterator([[3,5],[11,13],[17,19]]): # long time ....: for ep,eq,er in cartesian_product_iterator([[0,1,2,3],[0,1,2,3],[0,1,2,3]]): ....: for e2 in [0, 1, 2, 3, 4]: ....: n = p^ep * q^eq * r^er * 2^e2 ....: for _ in range(2): ....: a = Zmod(n).random_element() ....: if a.is_square().__xor__(a.__pari__().issquare()): ....: print(a, n)
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 """
cdef bint is_square_c(self) except -2: cdef int l2, m2 # We first try to rule out self being a square without # factoring the modulus. if lift & 2 == 2: # lift = 2 or 3 (mod 4) return 0 return 0 # self is a square modulo 2^m2. We compute the Jacobi symbol # modulo modd. If this is -1, then self is not a square. # We need to factor the modulus. We do it here instead of # letting PARI do it, so that we can cache the factorisation.
def sqrt(self, extend=True, all=False): r""" 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.
EXAMPLES::
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
::
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) []
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] """ return list(self.parent().square_roots_of_one()) else:
from .finite_field_constructor import FiniteField Q = FiniteField(self.__modulus.sageInteger**2, y, modulus) else: # TODO raise NotImplementedError raise ValueError("self must be a square")
cdef long e, exp, val
if self.is_zero(): # All multiples of p^ciel(e/2) vanish return [self._parent(x) for x in xrange(0, self.__modulus.sageInteger, p**((e+1)/2))] else: z = self.lift() val = z.valuation(p)/2 # square => valuation is even from sage.rings.finite_rings.integer_mod_ring import IntegerModRing # Find the unit part (mod the ring with appropriate precision) u = IntegerModRing(p**(e-val))(z // p**(2*val)) # will add multiples of p^exp exp = e - val if p == 2: exp -= 1 # note the factor of 2 below if 2*exp < e: exp = (e+1)/2 # For all a^2 = u and all integers b # (a*p^val + b*p^exp) ^ 2 # = u*p^(2*val) + 2*a*b*p^(val+exp) + b^2*p^(2*exp) # = u*p^(2*val) mod p^e # whenever min(val+exp, 2*exp) > e p_val = p**val p_exp = p**exp w = [self._parent(a.lift() * p_val + b) for a in u.sqrt(all=True) for b in xrange(0, self.__modulus.sageInteger, p_exp)] if p == 2: w = list(set(w)) w.sort() return w
else:
else: # Use CRT to combine together a square root modulo each prime power
else: # Use CRT to combine together all square roots modulo each prime power # Now combine in all possible ways using the CRT # x is a specific choice of roots modulo each prime power divisor
square_root = sqrt
def nth_root(self, n, extend = False, all = False, algorithm = None, cunningham = False): r""" 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).
NOTES:
- 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: 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]
TESTS::
sage: for p in [1009,2003,10007,100003]: ....: K = GF(p) ....: for r in (p-1).divisors(): ....: if r == 1: continue ....: x = K.random_element() ....: y = x^r ....: if y.nth_root(r)**r != y: raise RuntimeError ....: if (y^41).nth_root(41*r)**(41*r) != y^41: raise RuntimeError ....: if (y^307).nth_root(307*r)**(307*r) != y^307: raise RuntimeError
sage: for t in range(200): ....: n = randint(1,2^63) ....: K = Integers(n) ....: b = K.random_element() ....: e = randint(-2^62, 2^63) ....: try: ....: a = b.nth_root(e) ....: if a^e != b: ....: print(n, b, e, a) ....: raise NotImplementedError ....: except ValueError: ....: pass
We check that :trac:`13172` is resolved::
sage: mod(-1, 4489).nth_root(2, all=True) []
Check that the code path cunningham might be used::
sage: a = Mod(9,11) sage: a.nth_root(2, False, True, 'Johnston', cunningham = True) # optional - cunningham [3, 8]
ALGORITHMS:
- The default for prime modulus is currently an algorithm described in the following paper:
Johnston, Anna M. A generalized qth root algorithm. Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms. Baltimore, 1999: pp 929-930.
AUTHORS:
- David Roe (2010-2-13) """ raise NotImplementedError else: return self else: if all: return [self] else: return self # we should probably do a first pass to see if there are any solutions so that we don't get giant intermediate lists and waste time... else: else: else: return [] else: else: return K(p**(pval // n) * mod(upart, p**(k-pval)).nth_root(n, algorithm=algorithm).lift()) else: else: # now self is congruent to 1 mod 4 or 1 mod p (for odd p), so the power series for p-adic log converges. # Hensel lifting is probably better, but this is easier at the moment. if all: return [s*K(p*k+m.lift()) for k in range(p**(k-(2 if p==2 else 1))) for m in modp for s in sign] else: return self_orig else: else:
def _nth_root_naive(self, n): """ Computes all nth roots using brute force, for doc-testing.
TESTS::
sage: for n in range(2,100): # long time ....: K = Integers(n) ....: elist = list(range(1,min(2*n+2,100))) ....: for e in random_sublist(elist, 5/len(elist)): ....: for a in random_sublist(range(1,n), min((n+2)//2,10)/(n-1)): ....: b = K(a) ....: try: ....: L = b.nth_root(e, all=True) ....: if len(L) > 0: ....: c = b.nth_root(e) ....: except Exception: ....: L = [-1] ....: M = b._nth_root_naive(e) ....: if sorted(L) != M: ....: print("mod(%s, %s).nth_root(%s,all=True), mod(%s, %s)._nth_root_naive(%s)" % (a,n,e,a,n,e)) ....: if len(L) > 0 and (c not in L): ....: print("mod(%s, %s).nth_root(%s), mod(%s, %s).nth_root(%s,all=True)" % (a,n,e,a,n,e)) """ L = [] for a in self.parent(): if a**n == self: L.append(a) return L
def _balanced_abs(self): """ 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 probabilistic nature of the underlying algorithm. """ else:
def rational_reconstruction(self): """ 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
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 """
def crt(IntegerMod_abstract self, IntegerMod_abstract other): r""" 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
::
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
TESTS::
sage: mod(0,1).crt(mod(4,2^127)) 4 sage: mod(4,2^127).crt(mod(0,1)) 4 sage: mod(4,2^30).crt(mod(0,1)) 4 sage: mod(0,1).crt(mod(4,2^30)) 4 sage: mod(0,1).crt(mod(4,2^15)) 4 sage: mod(4,2^15).crt(mod(0,1)) 4
AUTHORS:
- Robert Bradshaw """ cdef int_fast64_t new_modulus
def additive_order(self): r""" 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 """
def is_primitive_root(self): """ 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() True sage: mod(11,1009^2).is_primitive_root() True
TESTS::
sage: for p in prime_range(3,12): ....: for k in range(1,4): ....: for even in [1,2]: ....: n = even*p^k ....: phin = euler_phi(n) ....: for _ in range(6): ....: a = Zmod(n).random_element() ....: if not a.is_unit(): continue ....: if a.is_primitive_root().__xor__(a.multiplicative_order()==phin): ....: print("mod(%s,%s) incorrect" % (a, n))
`0` is not a primitive root mod `n` (:trac:`23624`) except for `n=0`::
sage: mod(0, 17).is_primitive_root() False sage: all(not mod(0, n).is_primitive_root() for n in srange(2, 20)) True sage: mod(0, 1).is_primitive_root() True
sage: all(not mod(p^j, p^k).is_primitive_root() ....: for p in prime_range(3, 12) ....: for k in srange(1, 4) ....: for j in srange(0, k)) True """ # self**(p**(k-1)*(p-1)//q) = 1 for some q # iff mod(self,p)**((p-1)//q) = 1 for some q # Now self is modulo a prime and need the factorization of p-1. # No small factors remain: we need to do some real work. for qq, e in q.factor(): if self**((p-1)//qq) == 1: return False return True
def multiplicative_order(self): """ Returns the multiplicative order of self.
EXAMPLES::
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 """
def valuation(self, p): """ 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 the (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
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.
TESTS::
sage: R=ZZ.quo(12) sage: a=R(2) sage: b=R(4) sage: a.valuation(2) 1 sage: b.valuation(2) +Infinity sage: ZZ.quo(1024)(16).valuation(4) 2
"""
cpdef _floordiv_(self, right): """ Exact division for prime moduli, for compatibility with other fields.
EXAMPLES::
sage: GF(7)(3) // 5 2 """
def _repr_(self):
def _latex_(self):
def _integer_(self, ZZ=None):
def _rational_(self):
def _vector_(self): """ Return self as a vector of its parent viewed as a one-dimensional vector space.
This is to support prime finite fields, which are implemented as `IntegerMod` ring.
EXAMPLES::
sage: F.<a> = GF(13) sage: V = F.vector_space() sage: V(a) (1) """
###################################################################### # class IntegerMod_gmp ######################################################################
cdef class IntegerMod_gmp(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) """
def __cinit__(self):
cdef IntegerMod_gmp _new_c(self): cdef IntegerMod_gmp x
def __dealloc__(self):
cdef void set_from_mpz(self, mpz_t value): cdef sage.rings.integer.Integer modulus
cdef void set_from_long(self, long value): r""" EXAMPLES::
sage: p = next_prime(2^32) sage: GF(p)(int(p+1)) 1 """
cdef void set_from_ulong_fast(self, unsigned long value):
def __lshift__(IntegerMod_gmp self, k): r""" Performs a left shift by ``k`` bits.
For details, see :meth:`shift`.
EXAMPLES::
sage: e = Mod(19, 10^10) sage: e << 102 9443608576 """
def __rshift__(IntegerMod_gmp self, k): r""" Performs a right shift by ``k`` bits.
For details, see :meth:`shift`.
EXAMPLES::
sage: e = Mod(19, 10^10) sage: e >> 1 9 """
cdef shift(IntegerMod_gmp self, long k): r""" Performs a bit-shift specified by ``k`` on ``self``.
Suppose that ``self`` represents an integer `x` modulo `n`. If `k` is `k = 0`, returns `x`. If `k > 0`, shifts `x` to the left, that is, multiplies `x` by `2^k` and then returns the representative in the range `[0,n)`. If `k < 0`, shifts `x` to the right, that is, returns the integral part of `x` divided by `2^k`.
Note that, in any case, ``self`` remains unchanged.
INPUT:
- ``k`` - Integer of type ``long``
OUTPUT:
- Result of type ``IntegerMod_gmp``
EXAMPLES::
sage: e = Mod(19, 10^10) sage: e << 102 9443608576 sage: e >> 1 9 sage: e >> 4 1 """ cdef IntegerMod_gmp x return self else: else:
cpdef int _cmp_(left, right) except -2: """ EXAMPLES::
sage: mod(5,13^20) == mod(5,13^20) True sage: mod(5,13^20) == mod(-5,13^20) False sage: mod(5,13^20) == mod(-5,13) False """ cdef int i else:
cpdef bint is_one(IntegerMod_gmp self): """ 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 """
def __nonzero__(IntegerMod_gmp self): """ Returns ``True`` if this is not `0`, otherwise ``False``.
EXAMPLES::
sage: mod(13,5^23).is_zero() False sage: (mod(25,5^23)^23).is_zero() True """
cpdef bint is_unit(self): """ 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 """
def __crt(IntegerMod_gmp self, IntegerMod_gmp other): cdef IntegerMod_gmp lift, x cdef sage.rings.integer.Integer modulus, other_modulus
else: except ZeroDivisionError: raise ZeroDivisionError("moduli must be coprime")
def __copy__(IntegerMod_gmp self): cdef IntegerMod_gmp x x = self._new_c() mpz_set(x.value, self.value) return x
cpdef _add_(self, right): """ EXAMPLES::
sage: R = Integers(10^10) sage: R(7) + R(8) 15 """ cdef IntegerMod_gmp x
cpdef _sub_(self, right): """ EXAMPLES::
sage: R = Integers(10^10) sage: R(7) - R(8) 9999999999 """ cdef IntegerMod_gmp x
cpdef _neg_(self): """ EXAMPLES::
sage: -mod(5,10^10) 9999999995 sage: -mod(0,10^10) 0 """ cdef IntegerMod_gmp x
cpdef _mul_(self, right): """ EXAMPLES::
sage: R = Integers(10^11) sage: R(700000) * R(800000) 60000000000 """ cdef IntegerMod_gmp x
cpdef _div_(self, right): """ EXAMPLES::
sage: R = Integers(10^11) sage: R(3) / R(7) 71428571429 """
def __int__(self):
def __index__(self): """ Needed so integers modulo `n` can be used as list indices.
EXAMPLES::
sage: v = [1,2,3,4,5] sage: v[Mod(3,10^20)] 4 """
def __long__(self): return long(self.lift())
def __pow__(IntegerMod_gmp self, exp, m): # NOTE: m ignored, always use modulus of parent ring """ EXAMPLES: sage: R = Integers(10^10) sage: R(2)^1000 5668069376 sage: p = next_prime(11^10) sage: R = Integers(p) sage: R(9876)^(p-1) 1 sage: mod(3, 10^100)^-2 8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888889 sage: mod(2, 10^100)^-2 Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
TESTS:
We define ``0^0`` to be unity, :trac:`13894`::
sage: p = next_prime(11^10) sage: R = Integers(p) sage: R(0)^0 1
The value returned from ``0^0`` should belong to our ring::
sage: type(R(0)^0) == type(R(0)) True
When the modulus is ``1``, the only element in the ring is ``0`` (and it is equivalent to ``1``), so we return that instead::
sage: from sage.rings.finite_rings.integer_mod \ ....: import IntegerMod_gmp sage: zero = IntegerMod_gmp(Integers(1),0) sage: type(zero) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: zero^0 0
""" finally: sig_off()
def __invert__(IntegerMod_gmp self): """ Return the multiplicative inverse of self.
EXAMPLES::
sage: a = mod(3,10^100); type(a) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: ~a 6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667 sage: ~mod(2,10^100) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist. """ raise ZeroDivisionError("Inverse does not exist.")
cdef IntegerMod_gmp x else:
def lift(IntegerMod_gmp self): """ Lift an integer modulo `n` to the integers.
EXAMPLES::
sage: a = Mod(8943, 2^70); type(a) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: lift(a) 8943 sage: a.lift() 8943 """ cdef sage.rings.integer.Integer z
def __float__(self):
def __hash__(self): """ EXAMPLES::
sage: a = Mod(8943, 2^100) sage: hash(a) 8943 """
@coerce_binop def gcd(self, IntegerMod_gmp other): """ 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 """ # self = other = 0
###################################################################### # class IntegerMod_int ######################################################################
cdef class IntegerMod_int(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 """
cdef IntegerMod_int _new_c(self, int_fast32_t value):
cdef void set_from_mpz(self, mpz_t value):
cdef void set_from_long(self, long value):
cdef void set_from_ulong_fast(self, unsigned long value):
cdef void set_from_int(IntegerMod_int self, int_fast32_t ivalue): else:
cdef int_fast32_t get_int_value(IntegerMod_int self): return self.ivalue
cpdef int _cmp_(self, right) except -2: """ EXAMPLES::
sage: mod(5,13) == mod(-8,13) True sage: mod(5,13) == mod(8,13) False sage: mod(5,13) == mod(5,24) False sage: mod(0, 13) == 0 True sage: mod(0, 13) == int(0) True """ else:
cpdef bint is_one(IntegerMod_int self): """ 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 """
def __nonzero__(IntegerMod_int self): """ Returns ``True`` if this is not `0`, otherwise ``False``.
EXAMPLES::
sage: mod(13,5).is_zero() False sage: mod(25,5).is_zero() True """
cpdef bint is_unit(IntegerMod_int self): """ 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 """
def __crt(IntegerMod_int self, IntegerMod_int other): """ 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
AUTHORS:
- Robert Bradshaw """ cdef IntegerMod_int lift cdef int_fast32_t x
except ZeroDivisionError: raise ZeroDivisionError("moduli must be coprime")
def __copy__(IntegerMod_int self): cdef IntegerMod_int x = IntegerMod_int.__new__(IntegerMod_int) x._parent = self._parent x.__modulus = self.__modulus x.ivalue = self.ivalue return x
cpdef _add_(self, right): """ EXAMPLES::
sage: R = Integers(10) sage: R(7) + R(8) 5 """ cdef int_fast32_t x
cpdef _sub_(self, right): """ EXAMPLES::
sage: R = Integers(10) sage: R(7) - R(8) 9 """ cdef int_fast32_t x
cpdef _neg_(self): """ EXAMPLES::
sage: -mod(7,10) 3 sage: -mod(0,10) 0 """
cpdef _mul_(self, right): """ EXAMPLES::
sage: R = Integers(10) sage: R(7) * R(8) 6 """
cpdef _div_(self, right): """ EXAMPLES::
sage: R = Integers(10) sage: R(2)/3 4 """ else:
cdef int_fast32_t x
def __int__(IntegerMod_int self): """ TESTS::
sage: e = Mod(8, 31) sage: int(e) 8 """
def __index__(self): """ Needed so integers modulo `n` can be used as list indices.
EXAMPLES::
sage: v = [1,2,3,4,5] sage: v[Mod(10,7)] 4 """
def __long__(IntegerMod_int self):
def __lshift__(IntegerMod_int self, k): r""" Performs a left shift by ``k`` bits.
For details, see :meth:`shift`.
EXAMPLES::
sage: e = Mod(5, 2^10 - 1) sage: e << 5 160 sage: e * 2^5 160 """
def __rshift__(IntegerMod_int self, k): r""" Performs a right shift by ``k`` bits.
For details, see :meth:`shift`.
EXAMPLES::
sage: e = Mod(5, 2^10 - 1) sage: e << 5 160 sage: e * 2^5 160 """
cdef shift(IntegerMod_int self, int k): """ Performs a bit-shift specified by ``k`` on ``self``.
Suppose that ``self`` represents an integer `x` modulo `n`. If `k` is `k = 0`, returns `x`. If `k > 0`, shifts `x` to the left, that is, multiplies `x` by `2^k` and then returns the representative in the range `[0,n)`. If `k < 0`, shifts `x` to the right, that is, returns the integral part of `x` divided by `2^k`.
Note that, in any case, ``self`` remains unchanged.
INPUT:
- ``k`` - Integer of type ``int``
OUTPUT:
- Result of type ``IntegerMod_int``
WARNING:
For positive ``k``, if ``x << k`` overflows as a 32-bit integer, the result is meaningless.
EXAMPLES::
sage: e = Mod(5, 2^10 - 1) sage: e << 5 160 sage: e * 2^5 160 sage: e = Mod(8, 2^5 - 1) sage: e >> 3 1 """ return self else:
def __pow__(IntegerMod_int self, exp, m): # NOTE: m ignored, always use modulus of parent ring """ EXAMPLES: sage: R = Integers(10) sage: R(2)^10 4 sage: R = Integers(389) sage: R(7)^388 1
sage: mod(3, 100)^-1 67 sage: mod(3, 100)^-100000000 1
sage: mod(2, 100)^-1 Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist. sage: mod(2, 100)^-100000000 Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
TESTS:
We define ``0^0`` to be unity, :trac:`13894`::
sage: R = Integers(100) sage: R(0)^0 1
The value returned from ``0^0`` should belong to our ring::
sage: type(R(0)^0) == type(R(0)) True
When the modulus is ``1``, the only element in the ring is ``0`` (and it is equivalent to ``1``), so we return that instead::
sage: R = Integers(1) sage: R(0)^0 0
""" cdef long long_exp cdef int_fast32_t res cdef mpz_t res_mpz else: finally:
# Return 0 if the modulus is 1, otherwise return 1. else:
def __invert__(IntegerMod_int self): """ Return the multiplicative inverse of self.
EXAMPLES::
sage: ~mod(7,100) 43 sage: Mod(0,1)^-1 0 """ else: else:
def lift(IntegerMod_int self): """ Lift an integer modulo `n` to the integers.
EXAMPLES::
sage: a = Mod(8943, 2^10); type(a) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'> sage: lift(a) 751 sage: a.lift() 751 """ cdef sage.rings.integer.Integer z
def __float__(IntegerMod_int self):
def __hash__(self): """ EXAMPLES::
sage: a = Mod(89, 2^10) sage: hash(a) 89 """
cdef bint is_square_c(self) except -2: cdef int_fast32_t l2, lodd, m2, modd # We first try to rule out self being a square without # factoring the modulus. return 0 # self is a square modulo 2^m2. We compute the Jacobi symbol # modulo modd. If this is -1, then self is not a square. # We need to factor the modulus. We do it here instead of # letting PARI do it, so that we can cache the factorisation.
def sqrt(self, extend=True, all=False): r""" 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.
EXAMPLES::
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: GF(107)(0).sqrt(all=True) [0]
::
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] """ # Unless the modulus is tiny, test to see if we're in the really # easy case of n prime, n = 3 mod 4. # it's a non-zero square, sqrt(a) = a^(p+1)/4 else: elif not extend: raise ValueError("self must be a square") # Now we use a heuristic to guess whether or not it will # be faster to just brute-force search for squares in a c loop... # TODO: more tuning? else: return [] # Either it failed but extend was True, or the generic algorithm is better
def _balanced_abs(self): """ This function returns `x` or `-x`, whichever has a positive representative in `-n/2 < x \leq n/2`. """ else:
@coerce_binop def gcd(self, IntegerMod_int other): """ 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 """
### End of class
cdef int_fast32_t gcd_int(int_fast32_t a, int_fast32_t b): """ Returns the gcd of a and b
For use with IntegerMod_int
AUTHORS:
- Robert Bradshaw """ cdef int_fast32_t tmp
cdef int_fast32_t mod_inverse_int(int_fast32_t x, int_fast32_t n) except 0: """ Returns y such that xy=1 mod n
For use in IntegerMod_int
AUTHORS:
- Robert Bradshaw """ cdef int_fast32_t tmp, a, b, last_t, t, next_t, q return 0 # a = s * n + t * x
cdef int_fast32_t mod_pow_int(int_fast32_t base, int_fast32_t exp, int_fast32_t n): """ Returns base^exp mod n
For use in IntegerMod_int
EXAMPLES::
sage: z = Mod(2, 256) sage: z^8 0
AUTHORS:
- Robert Bradshaw """ cdef int_fast32_t prod, pow2
cdef int jacobi_int(int_fast32_t a, int_fast32_t m) except -2: """ Calculates the jacobi symbol (a/n)
For use in IntegerMod_int
AUTHORS:
- Robert Bradshaw """ cdef int_fast32_t b
elif a == 1: # Now a = 2^s * b
# factor out (2/m)^s term
# quadratic reciprocity
###################################################################### # class IntegerMod_int64 ######################################################################
cdef class IntegerMod_int64(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) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'> sage: loads(a.dumps()) == a True sage: Mod(5, 2^31) 5
AUTHORS:
- Robert Bradshaw (2006-09-14) """
cdef IntegerMod_int64 _new_c(self, int_fast64_t value): cdef IntegerMod_int64 x
cdef void set_from_mpz(self, mpz_t value):
cdef void set_from_long(self, long value):
cdef void set_from_ulong_fast(self, unsigned long value):
cdef void set_from_int(IntegerMod_int64 self, int_fast64_t ivalue): else:
cdef int_fast64_t get_int_value(IntegerMod_int64 self): return self.ivalue
cpdef int _cmp_(self, right) except -2: """ EXAMPLES::
sage: mod(5,13^5) == mod(13^5+5,13^5) True sage: mod(5,13^5) == mod(8,13^5) False sage: mod(5,13^5) == mod(5,13) True sage: mod(0, 13^5) == 0 True sage: mod(0, 13^5) == int(0) True """
cpdef bint is_one(IntegerMod_int64 self): """ 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 """
def __nonzero__(IntegerMod_int64 self): """ Returns ``True`` if this is not `0`, otherwise ``False``.
EXAMPLES::
sage: mod(13,5^10).is_zero() False sage: mod(5^12,5^10).is_zero() True """
cpdef bint is_unit(IntegerMod_int64 self): """ 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 """
def __crt(IntegerMod_int64 self, IntegerMod_int64 other): """ 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^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
AUTHORS:
- Robert Bradshaw """ cdef IntegerMod_int64 lift cdef int_fast64_t x
except ZeroDivisionError: raise ZeroDivisionError("moduli must be coprime")
def __copy__(IntegerMod_int64 self): return self._new_c(self.ivalue)
cpdef _add_(self, right): """ EXAMPLES::
sage: R = Integers(10^5) sage: R(7) + R(8) 15 """ cdef int_fast64_t x
cpdef _sub_(self, right): """ EXAMPLES::
sage: R = Integers(10^5) sage: R(7) - R(8) 99999 """ cdef int_fast64_t x
cpdef _neg_(self): """ EXAMPLES::
sage: -mod(7,10^5) 99993 sage: -mod(0,10^6) 0 """
cpdef _mul_(self, right): """ EXAMPLES::
sage: R = Integers(10^5) sage: R(700) * R(800) 60000 """
cpdef _div_(self, right): """ EXAMPLES::
sage: R = Integers(10^5) sage: R(2)/3 33334 """
def __int__(IntegerMod_int64 self):
def __index__(self): """ Needed so integers modulo `n` can be used as list indices.
EXAMPLES::
sage: v = [1,2,3,4,5] sage: v[Mod(3, 2^20)] 4 """
def __long__(IntegerMod_int64 self):
def __lshift__(IntegerMod_int64 self, k): r""" Performs a left shift by ``k`` bits.
For details, see :meth:`shift`.
EXAMPLES::
sage: e = Mod(5, 2^31 - 1) sage: e << 32 10 sage: e * 2^32 10 """
def __rshift__(IntegerMod_int64 self, k): r""" Performs a right shift by ``k`` bits.
For details, see :meth:`shift`.
EXAMPLES::
sage: e = Mod(5, 2^31 - 1) sage: e >> 1 2 """
cdef shift(IntegerMod_int64 self, int k): """ Performs a bit-shift specified by ``k`` on ``self``.
Suppose that ``self`` represents an integer `x` modulo `n`. If `k` is `k = 0`, returns `x`. If `k > 0`, shifts `x` to the left, that is, multiplies `x` by `2^k` and then returns the representative in the range `[0,n)`. If `k < 0`, shifts `x` to the right, that is, returns the integral part of `x` divided by `2^k`.
Note that, in any case, ``self`` remains unchanged.
INPUT:
- ``k`` - Integer of type ``int``
OUTPUT:
- Result of type ``IntegerMod_int64``
WARNING:
For positive ``k``, if ``x << k`` overflows as a 64-bit integer, the result is meaningless.
EXAMPLES::
sage: e = Mod(5, 2^31 - 1) sage: e << 32 10 sage: e * 2^32 10 sage: e = Mod(5, 2^31 - 1) sage: e >> 1 2 """ return self else:
def __pow__(IntegerMod_int64 self, exp, m): # NOTE: m ignored, always use modulus of parent ring """ EXAMPLES: sage: R = Integers(10) sage: R(2)^10 4 sage: p = next_prime(10^5) sage: R = Integers(p) sage: R(1234)^(p-1) 1 sage: R = Integers(17^5) sage: R(17)^5 0
sage: R(2)^-1 * 2 1 sage: R(2)^-1000000 * 2^1000000 1 sage: R(17)^-1 Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist. sage: R(17)^-100000000 Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
TESTS::
sage: type(R(0)) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>
We define ``0^0`` to be unity, :trac:`13894`::
sage: p = next_prime(10^5) sage: R = Integers(p) sage: R(0)^0 1
The value returned from ``0^0`` should belong to our ring::
sage: type(R(0)^0) == type(R(0)) True
When the modulus is ``1``, the only element in the ring is ``0`` (and it is equivalent to ``1``), so we return that instead::
sage: from sage.rings.finite_rings.integer_mod \ ....: import IntegerMod_int64 sage: zero = IntegerMod_int64(Integers(1),0) sage: type(zero) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'> sage: zero^0 0
""" cdef long long_exp cdef int_fast64_t res cdef mpz_t res_mpz else: else: res = mpz_get_pyintlong(res_mpz) finally:
# Return 0 if the modulus is 1, otherwise return 1. else:
def __invert__(IntegerMod_int64 self): """ Return the multiplicative inverse of self.
EXAMPLES::
sage: a = mod(7,2^40); type(a) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'> sage: ~a 471219269047 sage: a 7 """
def lift(IntegerMod_int64 self): """ Lift an integer modulo `n` to the integers.
EXAMPLES::
sage: a = Mod(8943, 2^25); type(a) <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'> sage: lift(a) 8943 sage: a.lift() 8943 """ cdef sage.rings.integer.Integer z
def __float__(IntegerMod_int64 self): """ Coerce self to a float.
EXAMPLES::
sage: a = Mod(8943, 2^35) sage: float(a) 8943.0 """
def __hash__(self): """ Compute hash of self.
EXAMPLES::
sage: a = Mod(8943, 2^35) sage: hash(a) 8943 """
def _balanced_abs(self): """ This function returns `x` or `-x`, whichever has a positive representative in `-n/2 < x \leq n/2`. """ else:
@coerce_binop def gcd(self, IntegerMod_int64 other): """ 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 """
### Helper functions
cdef mpz_pow_helper(mpz_t res, mpz_t base, object exp, mpz_t modulus): cdef long long_exp
else:
cdef int_fast64_t gcd_int64(int_fast64_t a, int_fast64_t b): """ Returns the gcd of a and b
For use with IntegerMod_int64
AUTHORS:
- Robert Bradshaw """ cdef int_fast64_t tmp
cdef int_fast64_t mod_inverse_int64(int_fast64_t x, int_fast64_t n) except 0: """ Returns y such that xy=1 mod n
For use in IntegerMod_int64
AUTHORS:
- Robert Bradshaw """ cdef int_fast64_t tmp, a, b, last_t, t, next_t, q # a = s * n + t * x
cdef int_fast64_t mod_pow_int64(int_fast64_t base, int_fast64_t exp, int_fast64_t n): """ Returns base^exp mod n
For use in IntegerMod_int64
AUTHORS:
- Robert Bradshaw """ cdef int_fast64_t prod, pow2
cdef int jacobi_int64(int_fast64_t a, int_fast64_t m) except -2: """ Calculates the jacobi symbol (a/n)
For use in IntegerMod_int64
AUTHORS:
- Robert Bradshaw """ cdef int s, jacobi = 1 cdef int_fast64_t b
a = a % m
while True: if a == 0: return 0 # gcd was nontrivial elif a == 1: return jacobi s = 0 while (1 << s) & a == 0: s += 1 b = a >> s # Now a = 2^s * b
# factor out (2/m)^s term if s % 2 == 1 and (m % 8 == 3 or m % 8 == 5): jacobi = -jacobi
if b == 1: return jacobi
# quadratic reciprocity if b % 4 == 3 and m % 4 == 3: jacobi = -jacobi a = m % b m = b
######################## # Square root functions ########################
def square_root_mod_prime_power(IntegerMod_abstract a, p, e): r""" 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.
AUTHORS:
- Robert Bradshaw
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
::
sage: a=Mod(72,97^10) sage: b=square_root_mod_prime_power(a,97,10) sage: b^2 == a True sage: mod(100, 5^7).sqrt()^2 100 """
return a # TODO: implement something that isn't totally idiotic.
# strip off even powers of p raise ValueError("self must be a square.") else:
# find square root of unit mod p
# lift p-adically using Newton iteration # this is done to higher precision than necessary except at the last step # need at least (e - val//2) p-adic digits of precision, which doubles # at each step
# multiply in powers of p (if any)
cpdef square_root_mod_prime(IntegerMod_abstract a, p=None): r""" 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:
- Siguna Muller. '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' (Chapter 30, Section 4) In Ph. Flajolet and P. Zimmermann, editors, Algorithms Seminar, 1991-1992. INRIA Research Report 1779, 1992, http://www.inria.fr/rrrt/rr-1779.html. 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
AUTHORS:
- Robert Bradshaw
TESTS:
Every case appears in the first hundred primes.
::
sage: from sage.rings.finite_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 """
cdef long r, m
cdef Integer resZ
return a
else:
else:
def lucas_q1(mm, IntegerMod_abstract P): """ 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:
.. [Pos88] \H. Postl. 'Fast evaluation of Dickson Polynomials' Contrib. to General Algebra, Vol. 6 (1988) pp. 223-225
AUTHORS:
- Robert Bradshaw
TESTS::
sage: from sage.rings.finite_rings.integer_mod import lucas_q1 sage: all([lucas_q1(k, a) == BinaryRecurrenceSequence(a, -1, 2, a)(k) ....: for a in Integers(23) ....: for k in range(13)]) True """
cdef sage.rings.integer.Integer m
cdef int j else: else:
def lucas(k, P, Q=1, n=None): r""" 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
.. MATH::
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:
.. [IEEEP1363] IEEE P1363 / D13 (Draft Version 13). Standard Specifications for Public Key Cryptography Annex A (Informative). Number-Theoretic Background. Section A.2.4
AUTHORS:
- Somindu Chaya Ramanna, Shashank Singh and Srinivas Vivek Venkatesh (2011-09-15, ECC2011 summer school)
- Robert Bradshaw
TESTS::
sage: from sage.rings.finite_rings.integer_mod import lucas sage: p = randint(0,100000) sage: q = randint(0,100000) sage: n = randint(0,100) sage: all([lucas(k,p,q,n)[0] == Mod(lucas_number2(k,p,q),n) ....: for k in Integers(20)]) True sage: from sage.rings.finite_rings.integer_mod import lucas sage: p = randint(0,100000) sage: q = randint(0,100000) sage: n = randint(0,100) sage: k = randint(0,100) sage: lucas(k,p,q,n) == [Mod(lucas_number2(k,p,q),n),Mod(q^(int(k/2)),n)] True
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] """ cdef IntegerMod_abstract p,q
raise ValueError
n = P.modulus()
else: p = P
else: q = Q
cdef sage.rings.integer.Integer m
cdef int j else:
############# Homomorphisms ###############
cdef class IntegerMod_hom(Morphism): cdef IntegerMod_abstract zero cdef NativeIntStruct modulus
def __init__(self, parent): # we need to use element constructor so that we can register both coercions and conversions using these morphisms.
cdef dict _extra_slots(self): """ Helper for pickling and copying.
EXAMPLES::
sage: R5 = IntegerModRing(5) sage: R15 = IntegerModRing(15) sage: phi = R5.coerce_map_from(R15); phi Natural morphism: From: Ring of integers modulo 15 To: Ring of integers modulo 5
This method helps to implement copying::
sage: psi = copy(phi); psi Natural morphism: From: Ring of integers modulo 15 To: Ring of integers modulo 5 sage: psi(R15(7)) 2 """
cdef _update_slots(self, dict _slots): """ Helper for pickling and copying.
EXAMPLES::
sage: R5 = IntegerModRing(5) sage: R15 = IntegerModRing(15) sage: phi = R5.coerce_map_from(R15); phi Natural morphism: From: Ring of integers modulo 15 To: Ring of integers modulo 5
This method helps to implement copying. ::
sage: psi = copy(phi); psi Natural morphism: From: Ring of integers modulo 15 To: Ring of integers modulo 5 sage: psi(R15(7)) 2
"""
cpdef Element _call_(self, x): return IntegerMod(self._codomain, x)
cdef class IntegerMod_to_IntegerMod(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] [<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>, <type '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] """ def __init__(self, R, S):
cpdef Element _call_(self, x): cdef IntegerMod_abstract a cdef unsigned long value
def _repr_type(self):
def is_surjective(self): r""" Return whether this morphism is surjective.
EXAMPLES::
sage: Zmod(4).hom(Zmod(2)).is_surjective() True
"""
def is_injective(self): r""" Return whether this morphism is injective.
EXAMPLES::
sage: Zmod(4).hom(Zmod(2)).is_injective() False
"""
cdef class Integer_to_IntegerMod(IntegerMod_hom): r""" 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] [<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type '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] """ def __init__(self, R):
cpdef Element _call_(self, x): cdef IntegerMod_abstract a cdef Py_ssize_t res res += self.modulus.int64 # if a._parent is not self._codomain: else:
def _repr_type(self):
def section(self):
def is_surjective(self): r""" Return whether this morphism is surjective.
EXAMPLES::
sage: ZZ.hom(Zmod(2)).is_surjective() True
"""
def is_injective(self): r""" Return whether this morphism is injective.
EXAMPLES::
sage: ZZ.hom(Zmod(2)).is_injective() False
"""
cdef class IntegerMod_to_Integer(Map): """ Map to lift elements to :class:`~sage.rings.integer.Integer`.
EXAMPLES::
sage: ZZ.convert_map_from(GF(2)) Lifting map: From: Finite Field of size 2 To: Integer Ring """ def __init__(self, R): """ TESTS:
Lifting maps are morphisms in the category of sets (see :trac:`15618`)::
sage: ZZ.convert_map_from(GF(2)).parent() Set of Morphisms from Finite Field of size 2 to Integer Ring in Category of sets """
cpdef Element _call_(self, x):
def _repr_type(self):
cdef class Int_to_IntegerMod(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] [<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>, <type '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] """ def __init__(self, R):
cpdef Element _call_(self, x): cdef IntegerMod_abstract a
cdef long res cdef int err
raise TypeError(f"{x} is not an integer")
cdef Integer z = Integer(x) a = zero._new_c_fast(0) a.set_from_mpz(z.value) return a
def _repr_type(self): |