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""" Ring `\ZZ` of Integers
The :class:`IntegerRing_class` represents the ring `\ZZ` of (arbitrary precision) integers. Each integer is an instance of :class:`Integer`, which is defined in a Pyrex extension module that wraps GMP integers (the ``mpz_t`` type in GMP).
::
sage: Z = IntegerRing(); Z Integer Ring sage: Z.characteristic() 0 sage: Z.is_field() False
There is a unique instance of the :class:`integer ring<IntegerRing_class>`. To create an :class:`Integer`, coerce either a Python int, long, or a string. Various other types will also coerce to the integers, when it makes sense.
::
sage: a = Z(1234); a 1234 sage: b = Z(5678); b 5678 sage: type(a) <type 'sage.rings.integer.Integer'> sage: a + b 6912 sage: Z('94803849083985934859834583945394') 94803849083985934859834583945394 """
#***************************************************************************** # Copyright (C) 2005 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 absolute_import, print_function
from cpython.int cimport * from cpython.list cimport * from cpython.object cimport Py_NE
from cysignals.signals cimport sig_check, sig_on, sig_off
from sage.libs.gmp.mpz cimport * import sage.rings.infinity import sage.rings.rational import sage.rings.rational_field import sage.rings.ideal import sage.libs.pari.all import sage.rings.ideal from sage.categories.basic import EuclideanDomains from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets from sage.structure.coerce cimport is_numpy_type from sage.structure.element cimport parent from sage.structure.parent_gens import ParentWithGens from sage.structure.parent cimport Parent from sage.structure.richcmp cimport rich_to_bool from sage.structure.sequence import Sequence
from sage.misc.misc_c import prod from sage.misc.randstate cimport randstate, current_randstate, SAGE_RAND_MAX from sage.libs.ntl.convert cimport ZZ_to_mpz
cimport sage.rings.integer as integer cimport sage.rings.rational as rational
from . import ring
arith = None cdef void late_import(): # A hack to avoid circular imports. global arith if arith is None: import sage.arith.all arith = sage.arith.all
cdef int number_of_integer_rings = 0
# Used by IntegerRing_class._randomize_mpz(): # When the user requests an integer sampled from a # DiscreteGaussianDistributionIntegerSampler with parameter sigma, we store the pair # (sigma, sampler) here. When the user requests an integer for the same # sigma, we do not recreate the sampler but take it from this "cache". _prev_discrete_gaussian_integer_sampler = (None, None)
def is_IntegerRing(x): r""" Internal function: return ``True`` iff ``x`` is the ring `\ZZ` of integers.
TESTS::
sage: from sage.rings.integer_ring import is_IntegerRing sage: is_IntegerRing(ZZ) True sage: is_IntegerRing(QQ) False sage: is_IntegerRing(parent(3)) True sage: is_IntegerRing(parent(1/3)) False """
cdef class IntegerRing_class(PrincipalIdealDomain): r""" The ring of integers.
In order to introduce the ring `\ZZ` of integers, we illustrate creation, calling a few functions, and working with its elements.
::
sage: Z = IntegerRing(); Z Integer Ring sage: Z.characteristic() 0 sage: Z.is_field() False sage: Z.category() Join of Category of euclidean domains and Category of infinite enumerated sets and Category of metric spaces sage: Z(2^(2^5) + 1) 4294967297
One can give strings to create integers. Strings starting with ``0x`` are interpreted as hexadecimal, and strings starting with ``0o`` are interpreted as octal::
sage: parent('37') <... 'str'> sage: parent(Z('37')) Integer Ring sage: Z('0x10') 16 sage: Z('0x1a') 26 sage: Z('0o20') 16
As an inverse to :meth:`~sage.rings.integer.Integer.digits`, lists of digits are accepted, provided that you give a base. The lists are interpreted in little-endian order, so that entry ``i`` of the list is the coefficient of ``base^i``::
sage: Z([4,1,7],base=100) 70104 sage: Z([4,1,7],base=10) 714 sage: Z([3, 7], 10) 73 sage: Z([3, 7], 9) 66 sage: Z([], 10) 0
Alphanumeric strings can be used for bases 2..36; letters ``a`` to ``z`` represent numbers 10 to 36. Letter case does not matter. ::
sage: Z("sage",base=32) 928270 sage: Z("SAGE",base=32) 928270 sage: Z("Sage",base=32) 928270 sage: Z([14, 16, 10, 28],base=32) 928270 sage: 14 + 16*32 + 10*32^2 + 28*32^3 928270
We next illustrate basic arithmetic in `\ZZ`::
sage: a = Z(1234); a 1234 sage: b = Z(5678); b 5678 sage: type(a) <type 'sage.rings.integer.Integer'> sage: a + b 6912 sage: b + a 6912 sage: a * b 7006652 sage: b * a 7006652 sage: a - b -4444 sage: b - a 4444
When we divide two integers using ``/``, the result is automatically coerced to the field of rational numbers, even if the result is an integer.
::
sage: a / b 617/2839 sage: type(a/b) <type 'sage.rings.rational.Rational'> sage: a/a 1 sage: type(a/a) <type 'sage.rings.rational.Rational'>
For floor division, use the ``//`` operator instead::
sage: a // b 0 sage: type(a//b) <type 'sage.rings.integer.Integer'>
Next we illustrate arithmetic with automatic coercion. The types that coerce are: str, int, long, Integer.
::
sage: a + 17 1251 sage: a * 374 461516 sage: 374 * a 461516 sage: a/19 1234/19 sage: 0 + Z(-64) -64
Integers can be coerced::
sage: a = Z(-64) sage: int(a) -64
We can create integers from several types of objects::
sage: Z(17/1) 17 sage: Z(Mod(19,23)) 19 sage: Z(2 + 3*5 + O(5^3)) 17
Arbitrary numeric bases are supported; strings or list of integers are used to provide the digits (more details in :class:`IntegerRing_class`)::
sage: Z("sage",base=32) 928270 sage: Z([14, 16, 10, 28],base=32) 928270
The :meth:`digits<~sage.rings.integer.Integer.digits>` method allows you to get the list of digits of an integer in a different basis (note that the digits are returned in little-endian order)::
sage: b = Z([4,1,7],base=100) sage: b 70104 sage: b.digits(base=71) [27, 64, 13]
sage: Z(15).digits(2) [1, 1, 1, 1] sage: Z(15).digits(3) [0, 2, 1]
The :meth:`str<~sage.rings.integer.Integer.str>` method returns a string of the digits, using letters ``a`` to ``z`` to represent digits 10..36::
sage: Z(928270).str(base=32) 'sage'
Note that :meth:`str<~sage.rings.integer.Integer.str>` only works with bases 2 through 36.
TESTS::
sage: TestSuite(ZZ).run() sage: list(ZZ) Traceback (most recent call last): ... NotImplementedError: len() of an infinite set """
def __init__(self): """ Initialize ``self``.
TESTS::
sage: from sage.rings.integer_ring import IntegerRing_class sage: A = IntegerRing_class()
We check that ``ZZ`` is an infinite enumerated set (see :trac:`16239`)::
sage: A in InfiniteEnumeratedSets() True """ convert_method_name='_integer_')
_element_constructor_ = integer.Integer
def __reduce__(self): """ For pickling.
TESTS::
sage: loads(dumps(ZZ)) is ZZ True """
def __hash__(self): """ Return the hash value of ``self``.
TESTS::
sage: from sage.rings.integer_ring import IntegerRing_class sage: A = IntegerRing_class() sage: A.__hash__() 554590422 """
def __richcmp__(left, right, int op): """ Rich comparison of ``left`` and ``right``.
TESTS::
sage: from sage.rings.integer_ring import IntegerRing_class sage: ZZ == ZZ True sage: ZZ != QQ True """
return rich_to_bool(op, 0)
def _repr_(self): """ Return a string representation of ``self``.
TESTS::
sage: ZZ # indirect doctest Integer Ring """
def _latex_(self): r""" Return a latex representation of ``self``.
TESTS::
sage: latex(ZZ) # indirect doctest \Bold{Z} """
def __getitem__(self, x): """ Return the ring `\ZZ[...]` obtained by adjoining to the integers one or several elements.
EXAMPLES::
sage: ZZ[sqrt(2), sqrt(3)] Relative Order in Number Field in sqrt2 with defining polynomial x^2 - 2 over its base field sage: ZZ['x'] Univariate Polynomial Ring in x over Integer Ring sage: ZZ['x,y'] Multivariate Polynomial Ring in x, y over Integer Ring sage: R = ZZ[sqrt(5) + 1]; R Order in Number Field in a with defining polynomial x^2 - 2*x - 4 sage: R.is_maximal() False sage: R = ZZ[(1+sqrt(5))/2]; R Order in Number Field in a with defining polynomial x^2 - x - 1 sage: R.is_maximal() True """ return self
def range(self, start, end=None, step=None): """ Optimized range function for Sage integers.
AUTHORS:
- Robert Bradshaw (2007-09-20)
EXAMPLES::
sage: ZZ.range(10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: ZZ.range(-5,5) [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4] sage: ZZ.range(0,50,5) [0, 5, 10, 15, 20, 25, 30, 35, 40, 45] sage: ZZ.range(0,50,-5) [] sage: ZZ.range(50,0,-5) [50, 45, 40, 35, 30, 25, 20, 15, 10, 5] sage: ZZ.range(50,0,5) [] sage: ZZ.range(50,-1,-5) [50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 0]
It uses different code if the step doesn't fit in a long::
sage: ZZ.range(0,2^83,2^80) [0, 1208925819614629174706176, 2417851639229258349412352, 3626777458843887524118528, 4835703278458516698824704, 6044629098073145873530880, 7253554917687775048237056, 8462480737302404222943232]
Make sure :trac:`8818` is fixed::
sage: ZZ.range(1r, 10r) [1, 2, 3, 4, 5, 6, 7, 8, 9] """ step = integer.Integer(step)
cdef int step_sign cdef long istep cdef integer.Integer zstep, last
else:
else: else:
def __iter__(self): """ Iterate over all integers: 0 1 -1 2 -2 3 -3 ...
EXAMPLES::
sage: for n in ZZ: ....: if n < 3: print(n) ....: else: break 0 1 -1 2 -2 """
cdef Integer _coerce_ZZ(self, ZZ_c *z):
cpdef _coerce_map_from_(self, S): r""" ``x`` canonically coerces to the integers `\ZZ` only if ``x`` is an int, long or already an element of `\ZZ`.
EXAMPLES::
sage: ZZ.coerce(int(5)) # indirect doctest 5 sage: ZZ.coerce(GF(7)(2)) Traceback (most recent call last): ... TypeError: no canonical coercion from Finite Field of size 7 to Integer Ring
The rational number ``3/1 == 3`` does not canonically coerce into the integers, since there is no canonical coercion map from the full field of rational numbers to the integers.
::
sage: a = 3/1; parent(a) Rational Field sage: ZZ(a) 3 sage: ZZ.coerce(a) Traceback (most recent call last): ... TypeError: no canonical coercion from Rational Field to Integer Ring
Coercions are available from numpy integer types::
sage: import numpy sage: ZZ.coerce(numpy.int8('1')) 1 sage: ZZ.coerce(numpy.int32('32')) 32 sage: ZZ.coerce(numpy.int64('-12')) -12 sage: ZZ.coerce(numpy.uint64('11')) 11
TESTS::
sage: 5r + True 6 sage: 5 + True 6
sage: f = ZZ.coerce_map_from(int); f Native morphism: From: Set of Python objects of class 'int' To: Integer Ring sage: f(4r) 4 sage: f(-7r) -7
Note that the input *MUST* be an ``int``::
sage: a = 10000000000000000000000rL sage: f(a) Traceback (most recent call last): ... TypeError: must be a Python int object """ return sage.rings.integer.long_to_Z() return sage.rings.integer.int_to_Z()
def random_element(self, x=None, y=None, distribution=None): r""" Return a random integer.
INPUT:
- ``x``, ``y`` integers -- bounds for the result.
- ``distribution``-- a string: - ``'uniform'`` - ``'mpz_rrandomb'`` - ``'1/n'`` - ``'gaussian'``
OUTPUT:
- With no input, return a random integer.
If only one integer `x` is given, return an integer between 0 and `x-1`.
If two integers are given, return an integer between `x` and `y-1` inclusive.
If at least one bound is given, the default distribution is the uniform distribution; otherwise, it is the distribution described below.
If the distribution ``'1/n'`` is specified, the bounds are ignored.
If the distribution ``'mpz_rrandomb'`` is specified, the output is in the range from 0 to `2^x - 1`.
If the distribution ``'gaussian'`` is specified, the output is sampled from a discrete Gaussian distribution with parameter `\sigma=x` and centered at zero. That is, the integer `v` is returned with probability proportional to `\mathrm{exp}(-v^2/(2\sigma^2))`. See :mod:`sage.stats.distributions.discrete_gaussian_integer` for details. Note that if many samples from the same discrete Gaussian distribution are needed, it is faster to construct a :class:`sage.stats.distributions.discrete_gaussian_integer.DiscreteGaussianDistributionIntegerSampler` object which is then repeatedly queried.
The default distribution for ``ZZ.random_element()`` is based on `X = \mbox{trunc}(4/(5R))`, where `R` is a random variable uniformly distributed between `-1` and `1`. This gives `\mbox{Pr}(X = 0) = 1/5`, and `\mbox{Pr}(X = n) = 2/(5|n|(|n|+1))` for `n \neq 0`. Most of the samples will be small; `-1`, `0`, and `1` occur with probability `1/5` each. But we also have a small but non-negligible proportion of "outliers"; `\mbox{Pr}(|X| \geq n) = 4/(5n)`, so for instance, we expect that `|X| \geq 1000` on one in 1250 samples.
We actually use an easy-to-compute truncation of the above distribution; the probabilities given above hold fairly well up to about `|n| = 10000`, but around `|n| = 30000` some values will never be returned at all, and we will never return anything greater than `2^{30}`.
EXAMPLES::
sage: [ZZ.random_element() for _ in range(10)] [-8, 2, 0, 0, 1, -1, 2, 1, -95, -1]
The default uniform distribution is integers in `[-2, 2]`::
sage: [ZZ.random_element(distribution="uniform") for _ in range(10)] [2, -2, 2, -2, -1, 1, -1, 2, 1, 0]
Here we use the distribution ``'1/n'``::
sage: [ZZ.random_element(distribution="1/n") for _ in range(10)] [-6, 1, -1, 1, 1, -1, 1, -1, -3, 1]
If a range is given, the default distribution is uniform in that range::
sage: ZZ.random_element(-10,10) -2 sage: ZZ.random_element(10) 2 sage: ZZ.random_element(10^50) 9531604786291536727294723328622110901973365898988 sage: [ZZ.random_element(5) for _ in range(10)] [3, 1, 2, 3, 0, 0, 3, 4, 0, 3]
Notice that the right endpoint is not included::
sage: [ZZ.random_element(-2,2) for _ in range(10)] [1, -2, -2, -1, -2, -1, -1, -2, 0, -2]
We compute a histogram over 1000 samples of the default distribution::
sage: from collections import defaultdict sage: d = defaultdict(lambda: 0) sage: for _ in range(1000): ....: samp = ZZ.random_element() ....: d[samp] = d[samp] + 1
sage: sorted(d.items()) [(-1955, 1), (-1026, 1), (-357, 1), (-248, 1), (-145, 1), (-81, 1), (-80, 1), (-79, 1), (-75, 1), (-69, 1), (-68, 1), (-63, 2), (-61, 1), (-57, 1), (-50, 1), (-37, 1), (-35, 1), (-33, 1), (-29, 2), (-27, 1), (-25, 1), (-23, 2), (-22, 3), (-20, 1), (-19, 1), (-18, 1), (-16, 4), (-15, 3), (-14, 1), (-13, 2), (-12, 2), (-11, 2), (-10, 7), (-9, 3), (-8, 3), (-7, 7), (-6, 8), (-5, 13), (-4, 24), (-3, 34), (-2, 75), (-1, 206), (0, 208), (1, 189), (2, 63), (3, 35), (4, 13), (5, 11), (6, 10), (7, 4), (8, 3), (10, 1), (11, 1), (12, 1), (13, 1), (14, 1), (16, 3), (18, 2), (19, 1), (26, 2), (27, 1), (28, 2), (29, 1), (30, 1), (32, 1), (33, 2), (35, 1), (37, 1), (39, 1), (41, 1), (42, 1), (52, 1), (91, 1), (94, 1), (106, 1), (111, 1), (113, 2), (132, 1), (134, 1), (232, 1), (240, 1), (2133, 1), (3636, 1)]
We return a sample from a discrete Gaussian distribution::
sage: ZZ.random_element(11.0, distribution="gaussian") 5
"""
cdef int _randomize_mpz(self, mpz_t value, x, y, distribution) except -1: """ This is an internal function, called by random_element.
INPUT:
- ``value`` -- this is the variable in which the answer will be returned
- ``x, y, distribution`` -- see :meth:`random_element`
TESTS::
sage: ZZ.random_element() # indirect doctest # random 6 """ cdef integer.Integer r cdef integer.Integer n_max, n_min, n_width else: else: n_min = self(-2) n_width = self(5) if x is None: raise ValueError("must specify x to use 'distribution=mpz_rrandomb'") mpz_rrandomb(value, rstate.gmp_state, int(x)) global _prev_discrete_gaussian_integer_sampler r = _prev_discrete_gaussian_integer_sampler[1]() else: else: raise ValueError("Unknown distribution for the integers: %s" % distribution)
def _is_valid_homomorphism_(self, codomain, im_gens): r""" Tests whether the map from `\ZZ` to codomain, which takes the generator of `\ZZ` to ``im_gens[0]``, is a ring homomorphism. (This amounts to checking that 1 goes to 1.)
TESTS::
sage: ZZ._is_valid_homomorphism_(ZZ,[1]) True sage: ZZ._is_valid_homomorphism_(ZZ,[2]) False sage: ZZ._is_valid_homomorphism_(ZZ.quotient_ring(8),[ZZ.quotient_ring(8)(1)]) True """ except TypeError: return False
def is_noetherian(self): """ Return ``True`` since the integers are a Noetherian ring.
EXAMPLES::
sage: ZZ.is_noetherian() True """
def _repr_option(self, key): """ Metadata about the :meth:`_repr_` output.
See :meth:`sage.structure.parent._repr_option` for details.
EXAMPLES::
sage: ZZ._repr_option('element_is_atomic') True """
def is_field(self, proof = True): """ Return ``False`` since the integers are not a field.
EXAMPLES::
sage: ZZ.is_field() False """
def is_finite(self): """ Return ``False`` since the integers are an infinite ring.
EXAMPLES::
sage: ZZ.is_finite() False """
def fraction_field(self): """ Return the field of rational numbers - the fraction field of the integers.
EXAMPLES::
sage: ZZ.fraction_field() Rational Field sage: ZZ.fraction_field() == QQ True """
def extension(self, poly, names, **kwds): """ Return the order generated by the specified list of polynomials.
INPUT:
- ``poly`` -- a list of one or more polynomials
- ``names`` -- a parameter which will be passed to :func:`EquationOrder`.
- ``embedding`` -- a parameter which will be passed to :func:`EquationOrder`.
OUTPUT:
- Given a single polynomial as input, return the order generated by a root of the polynomial in the field generated by a root of the polynomial.
Given a list of polynomials as input, return the relative order generated by a root of the first polynomial in the list, over the order generated by the roots of the subsequent polynomials.
EXAMPLES::
sage: ZZ.extension(x^2-5, 'a') Order in Number Field in a with defining polynomial x^2 - 5 sage: ZZ.extension([x^2 + 1, x^2 + 2], 'a,b') Relative Order in Number Field in a with defining polynomial x^2 + 1 over its base field """
def quotient(self, I, names=None): r""" Return the quotient of `\ZZ` by the ideal or integer ``I``.
EXAMPLES::
sage: ZZ.quo(6*ZZ) Ring of integers modulo 6 sage: ZZ.quo(0*ZZ) Integer Ring sage: ZZ.quo(3) Ring of integers modulo 3 sage: ZZ.quo(3*QQ) Traceback (most recent call last): ... TypeError: I must be an ideal of ZZ """ else: raise TypeError("I must be an ideal of ZZ or an integer")
def residue_field(self, prime, check = True): r""" Return the residue field of the integers modulo the given prime, i.e. `\ZZ/p\ZZ`.
INPUT:
- ``prime`` - a prime number
- ``check`` - (boolean, default ``True``) whether or not to check the primality of prime.
OUTPUT: The residue field at this prime.
EXAMPLES::
sage: F = ZZ.residue_field(61); F Residue field of Integers modulo 61 sage: pi = F.reduction_map(); pi Partially defined reduction map: From: Rational Field To: Residue field of Integers modulo 61 sage: pi(123/234) 6 sage: pi(1/61) Traceback (most recent call last): ... ZeroDivisionError: Cannot reduce rational 1/61 modulo 61: it has negative valuation sage: lift = F.lift_map(); lift Lifting map: From: Residue field of Integers modulo 61 To: Integer Ring sage: lift(F(12345/67890)) 33 sage: (12345/67890) % 61 33
Construction can be from a prime ideal instead of a prime::
sage: ZZ.residue_field(ZZ.ideal(97)) Residue field of Integers modulo 97
TESTS::
sage: ZZ.residue_field(ZZ.ideal(96)) Traceback (most recent call last): ... TypeError: Principal ideal (96) of Integer Ring is not prime sage: ZZ.residue_field(96) Traceback (most recent call last): ... TypeError: 96 is not prime """ raise TypeError("%s is not an ideal of ZZ" % prime) else: raise TypeError("%s is neither an ideal of ZZ nor an integer" % prime)
def gens(self): """ Return the tuple ``(1,)`` containing a single element, the additive generator of the integers, which is 1.
EXAMPLES::
sage: ZZ.gens(); ZZ.gens()[0] (1,) 1 sage: type(ZZ.gens()[0]) <type 'sage.rings.integer.Integer'> """
def gen(self, n=0): """ Return the additive generator of the integers, which is 1.
INPUT:
- ``n`` (default: 0) -- In a ring with more than one generator, the optional parameter `n` indicates which generator to return; since there is only one generator in this case, the only valid value for `n` is 0.
EXAMPLES::
sage: ZZ.gen() 1 sage: type(ZZ.gen()) <type 'sage.rings.integer.Integer'> """ else: raise IndexError("n must be 0")
def ngens(self): """ Return the number of additive generators of the ring, which is 1.
EXAMPLES::
sage: ZZ.ngens() 1 sage: len(ZZ.gens()) 1 """
def degree(self): """ Return the degree of the integers, which is 1.
Here, degree refers to the rank of the ring as a module over the integers.
EXAMPLES::
sage: ZZ.degree() 1 """
def absolute_degree(self): """ Return the absolute degree of the integers, which is 1.
Here, absolute degree refers to the rank of the ring as a module over the integers.
EXAMPLES::
sage: ZZ.absolute_degree() 1 """
def characteristic(self): """ Return the characteristic of the integers, which is 0.
EXAMPLES::
sage: ZZ.characteristic() 0 """
def krull_dimension(self): """ Return the Krull dimension of the integers, which is 1.
EXAMPLES::
sage: ZZ.krull_dimension() 1 """
def is_integrally_closed(self): """ Return that the integer ring is, in fact, integrally closed.
EXAMPLES::
sage: ZZ.is_integrally_closed() True """
def completion(self, p, prec, extras = {}): r""" Return the metric completion of the integers at the prime `p`.
INPUT:
- ``p`` -- a prime (or ``infinity``)
- ``prec`` -- the desired precision
- ``extras`` -- any further parameters to pass to the method used to create the completion.
OUTPUT:
- The completion of `\ZZ` at `p`.
EXAMPLES::
sage: ZZ.completion(infinity, 53) Integer Ring sage: ZZ.completion(5, 15, {'print_mode': 'bars'}) 5-adic Ring with capped relative precision 15 """ else:
def order(self): """ Return the order (cardinality) of the integers, which is ``+Infinity``.
EXAMPLES::
sage: ZZ.order() +Infinity """
def zeta(self, n=2): """ Return a primitive ``n``-th root of unity in the integers, or raise an error if none exists.
INPUT:
- ``n`` -- (default 2) a positive integer
OUTPUT:
- an ``n``-th root of unity in `\ZZ`.
EXAMPLES::
sage: ZZ.zeta() -1 sage: ZZ.zeta(1) 1 sage: ZZ.zeta(3) Traceback (most recent call last): ... ValueError: no nth root of unity in integer ring sage: ZZ.zeta(0) Traceback (most recent call last): ... ValueError: n must be positive in zeta() """ else:
def parameter(self): r""" Return an integer of degree 1 for the Euclidean property of `\ZZ`, namely 1.
EXAMPLES::
sage: ZZ.parameter() 1 """
def _roots_univariate_polynomial(self, p, ring=None, multiplicities=True, algorithm=None): r""" Return the roots of the univariate polynomial ``p``.
INPUT:
- ``p`` -- univariate integer polynomial
- ``ring`` -- ring (default: ``None``); a ring containing `\ZZ` to compute the roots in; ``None`` is equivalent to ``ZZ``
- ``multiplicities`` -- boolean (default: ``True``); whether to compute the multiplicities
- ``algorithm`` -- ``"dense"``, ``"sparse"`` or ``None`` (default: ``None``); the algorithm to use
OUTPUT:
- If ``multiplicities=True``, the list of pairs `(r, n)` where `r` is a root and `n` the corresponding multiplicity;
- If ``multiplicities=False``, the list of distincts roots with no information about the multiplicities.
ALGORITHM:
If ``algorithm`` is ``"dense"`, the roots are computed using :meth:`_roots_from_factorization`.
If ``algorithm`` is ``"sparse"``, the roots are computed using the algorithm described in [CKS1999]_.
If ``algorithm`` is ``None``, use the ``"dense"`` algorithm for polynomials of degree at most `100`, and ``"sparse"`` otherwise.
.. NOTE::
This is a helper method for :meth:`sage.rings.polynomial.polynomial_element.Polynomial.roots`.
TESTS::
sage: R.<x> = PolynomialRing(ZZ, sparse=True) sage: p = (x + 1)^23 * (x - 1)^23 * (x - 100) * (x + 5445)^5 sage: ZZ._roots_univariate_polynomial(p) [(100, 1), (-5445, 5), (1, 23), (-1, 23)] sage: p *= (1 + x^3458645 - 76*x^3435423343 + x^45346567867756556) sage: ZZ._roots_univariate_polynomial(p) [(1, 23), (-1, 23), (100, 1), (-5445, 5)] sage: p *= x^156468451540687043504386074354036574634735074 sage: ZZ._roots_univariate_polynomial(p) [(0, 156468451540687043504386074354036574634735074), (1, 23), (-1, 23), (100, 1), (-5445, 5)] sage: ZZ._roots_univariate_polynomial(p, multiplicities=False) [0, 1, -1, 100, -5445]
sage: R.<x> = PolynomialRing(ZZ, sparse=False) sage: p = (x + 1)^23 * (x - 1)^23 * (x - 100) * (x + 5445)^5 sage: ZZ._roots_univariate_polynomial(p) [(100, 1), (-5445, 5), (1, 23), (-1, 23)] sage: ZZ._roots_univariate_polynomial(p, multiplicities=False) [100, -5445, 1, -1]
sage: ZZ._roots_univariate_polynomial(p, algorithm="sparse") [(100, 1), (-5445, 5), (1, 23), (-1, 23)] sage: ZZ._roots_univariate_polynomial(p, algorithm="dense") [(100, 1), (-5445, 5), (1, 23), (-1, 23)] sage: ZZ._roots_univariate_polynomial(p, algorithm="foobar") Traceback (most recent call last): ... ValueError: unknown algorithm 'foobar'
sage: p = x^20 * p sage: ZZ._roots_univariate_polynomial(p, algorithm="sparse") [(0, 20), (100, 1), (-5445, 5), (1, 23), (-1, 23)] sage: ZZ._roots_univariate_polynomial(p, algorithm="dense") [(100, 1), (-5445, 5), (0, 20), (1, 23), (-1, 23)] """ raise ValueError("roots of 0 are not defined")
# A specific algorithm is available only for integer roots of integer polynomials
# Automatic choice of algorithm else:
# Check if the polynomial is a constant, in which case there are # no roots. Note that the polynomial is not 0. return []
# The dense algorithm is to compute the roots from the factorization.
cdef list roots
# Root 0 return roots else:
# totally dense polynomial
p = p.map_coefficients(lambda c: c // cont)
# Looking for "large" gaps in the exponents # These gaps split the polynomial into lower degree components # Roots of modulus > 1 are common roots of the components break else:
# if no gap, directly return the roots of p roots.extend(p._roots_from_factorization(p.factor(), multiplicities)) return roots
cdef list cc cdef list ee cdef int m1, m2 cdef bint b1, b2 # Computation of the roots of modulus 1, without multiplicities # 1 is root iff p(1) == 0 ; -1 iff p(-1) == 0
# Computation of the roots of modulus 1, with multiplicities # For the multiplicities, take the derivatives else:
# Stop asap
# Sparse derivative, that is (p/x^v)' where v = p.val():
# Add roots of modulus > 1 to `roots`: else:
################################# ## Coercions to interfaces ################################# def _gap_init_(self): """ Return a GAP representation of ``self``.
EXAMPLES::
sage: gap(ZZ) # indirect doctest Integers """
def _magma_init_(self, magma): """ Return a magma representation of ``self``.
EXAMPLES::
sage: magma(ZZ) # indirect doctest, optional - magma Integer Ring """ return 'IntegerRing()'
def _macaulay2_init_(self): """ Return a macaulay2 representation of ``self``.
EXAMPLES::
sage: macaulay2(ZZ) #optional - macaulay2 ZZ """ return "ZZ"
def _polymake_init_(self): r""" Return the polymake representation of the integer ring.
EXAMPLES::
sage: polymake(ZZ) # optional - polymake # indirect doctest Integer
""" return '"Integer"'
def _sage_input_(self, sib, coerced): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: sage_input(ZZ, verify=True) # Verified ZZ sage: from sage.misc.sage_input import SageInputBuilder sage: ZZ._sage_input_(SageInputBuilder(), False) {atomic:ZZ} """
def valuation(self, p): r""" Return the discrete valuation with uniformizer ``p``.
EXAMPLES::
sage: v = ZZ.valuation(3); v 3-adic valuation sage: v(3) 1
.. SEEALSO::
:meth:`Order.valuation() <sage.rings.number_field.order.Order.valuation>`, :meth:`RationalField.valuation() <sage.rings.rational_field.RationalField.valuation>`
"""
ZZ = IntegerRing_class() Z = ZZ
def IntegerRing(): """ Return the integer ring.
EXAMPLES::
sage: IntegerRing() Integer Ring sage: ZZ==IntegerRing() True """
def crt_basis(X, xgcd=None): r""" Compute and return a Chinese Remainder Theorem basis for the list ``X`` of coprime integers.
INPUT:
- ``X`` -- a list of Integers that are coprime in pairs.
- ``xgcd`` -- an optional parameter which is ignored.
OUTPUT:
- ``E`` - a list of Integers such that ``E[i] = 1`` (mod ``X[i]``) and ``E[i] = 0`` (mod ``X[j]``) for all `j \neq i`.
For this explanation, let ``E[i]`` be denoted by `E_i`.
The `E_i` have the property that if `A` is a list of objects, e.g., integers, vectors, matrices, etc., where `A_i` is understood modulo `X_i`, then a CRT lift of `A` is simply
.. MATH::
\sum_i E_i A_i.
ALGORITHM: To compute `E_i`, compute integers `s` and `t` such that
.. MATH::
s X_i + t \prod_{i \neq j} X_j = 1. (\*)
Then
.. MATH::
E_i = t \prod_{i \neq j} X[j].
Notice that equation (\*) implies that `E_i` is congruent to 1 modulo `X_i` and to 0 modulo the other `X_j` for `j \neq i`.
COMPLEXITY: We compute ``len(X)`` extended GCD's.
EXAMPLES::
sage: X = [11,20,31,51] sage: E = crt_basis([11,20,31,51]) sage: E[0]%X[0], E[1]%X[0], E[2]%X[0], E[3]%X[0] (1, 0, 0, 0) sage: E[0]%X[1], E[1]%X[1], E[2]%X[1], E[3]%X[1] (0, 1, 0, 0) sage: E[0]%X[2], E[1]%X[2], E[2]%X[2], E[3]%X[2] (0, 0, 1, 0) sage: E[0]%X[3], E[1]%X[3], E[2]%X[3], E[3]%X[3] (0, 0, 0, 1) """ raise TypeError("X must be a list") return []
# 2. Compute extended GCD's raise ArithmeticError("the elements of the list X must be coprime in pairs") |