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
""" Dense univariate polynomials over `\ZZ/n\ZZ`, implemented using NTL.
This implementation is generally slower than the FLINT implementation in :mod:`~sage.rings.polynomial.polynomial_zmod_flint`, so we use FLINT by default when the modulus is small enough; but NTL does not require that `n` be ``int``-sized, so we use it as default when `n` is too large for FLINT.
Note that the classes :class:`Polynomial_dense_modn_ntl_zz` and :class:`Polynomial_dense_modn_ntl_ZZ` are different; the former is limited to moduli less than a certain bound, while the latter supports arbitrarily large moduli.
AUTHORS:
- Robert Bradshaw: Split off from polynomial_element_generic.py (2007-09) - Robert Bradshaw: Major rewrite to use NTL directly (2007-09) """
#***************************************************************************** # Copyright (C) 2007 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
from cysignals.memory cimport sig_malloc, sig_free from cysignals.signals cimport sig_on, sig_off
from sage.rings.polynomial.polynomial_element cimport Polynomial, _dict_to_list
from sage.libs.ntl.types cimport NTL_SP_BOUND from sage.libs.ntl.ZZ_p cimport * from sage.libs.ntl.lzz_p cimport * from sage.libs.ntl.lzz_pX cimport * from sage.libs.ntl.ZZ_pX cimport *
cdef class Polynomial_dense_mod_n(Polynomial): """ A dense polynomial over the integers modulo n, where n is composite, with the underlying arithmetic done using NTL.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(16), implementation='NTL') sage: f = x^3 - x + 17 sage: f^2 x^6 + 14*x^4 + 2*x^3 + x^2 + 14*x + 1
sage: loads(f.dumps()) == f True
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: p = 3*x sage: q = 7*x sage: p+q 10*x sage: R.<x> = PolynomialRing(Integers(8), implementation='NTL') sage: parent(p) Univariate Polynomial Ring in x over Ring of integers modulo 100 (using NTL) sage: p + q 10*x sage: R({10:-1}) 7*x^10
TESTS::
sage: f = Integers(5*2^100)['x'].random_element() sage: from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n sage: isinstance(f, Polynomial_dense_mod_n) True
""" def __init__(self, parent, x=None, check=True, is_gen=False, construct=False): cdef Polynomial_dense_mod_n numer, denom
self.__poly = ZZ_pX(x, parent.modulus()) return
self.__poly = (<Polynomial_dense_modn_ntl_zz>x).__poly.__copy__() return else:
self.__poly = x.copy() return
isinstance(x.numerator(), Polynomial_dense_mod_n): if x.denominator().is_unit(): numer = x.numerator() denom = x.denominator().inverse_of_unit() x = numer.__poly * denom.__poly check = False else: raise TypeError("Denominator not a unit.")
def __reduce__(self):
def int_list(self):
def __pari__(self, variable=None): """ EXAMPLES::
sage: t = PolynomialRing(IntegerModRing(17),"t", implementation='NTL').gen() sage: f = t^3 + 3*t - 17 sage: pari(f) Mod(1, 17)*t^3 + Mod(3, 17)*t """
def ntl_ZZ_pX(self): r""" Return underlying NTL representation of this polynomial. Additional ''bonus'' functionality is available through this function.
.. warning::
You must call ``ntl.set_modulus(ntl.ZZ(n))`` before doing arithmetic with this object! """
cdef get_unsafe(self, Py_ssize_t n): """ Return the `n`-th coefficient of ``self``.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n sage: f = Polynomial_dense_mod_n(R,[5,10,13,1,4]); f 4*x^4 + x^3 + 13*x^2 + 10*x + 5 sage: f[2] 13 sage: f[:3] 13*x^2 + 10*x + 5 """
def _unsafe_mutate(self, n, value): n = int(n) if n < 0: raise IndexError("n must be >= 0") self.__poly[n] = int(value)
def _pow(self, n): n = int(n)
if self.degree() <= 0: return self.parent()(self[0]**n) if n < 0: return (~self)**(-n) return self.parent()(self.__poly**n, construct=True)
cpdef _add_(self, right):
cpdef _mul_(self, right): """ EXAMPLES::
sage: x = PolynomialRing(Integers(100), 'x', implementation='NTL').0 sage: (x - 2)*(x^2 - 8*x + 16) x^3 + 90*x^2 + 32*x + 68 """
cpdef _lmul_(self, Element c): except RuntimeError as msg: # should this really be a TypeError raise TypeError(msg)
""" Returns a tuple (quotient, remainder) where self = quotient*other + remainder. """
def shift(self, n): r""" Returns this polynomial multiplied by the power `x^n`. If `n` is negative, terms below `x^n` will be discarded. Does not change this polynomial.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(12345678901234567890), implementation='NTL') sage: p = x^2 + 2*x + 4 sage: p.shift(0) x^2 + 2*x + 4 sage: p.shift(-1) x + 2 sage: p.shift(-5) 0 sage: p.shift(2) x^4 + 2*x^3 + 4*x^2
TESTS::
sage: p = R(0) sage: p.shift(3).is_zero() True sage: p.shift(-3).is_zero() True
AUTHOR:
- David Harvey (2006-08-06) """ if n == 0 or self.degree() < 0: return self return self.parent()(self.__poly.left_shift(n), construct=True)
cpdef _sub_(self, right):
def __floordiv__(self, right):
def degree(self, gen=None): """ Return the degree of this polynomial. The zero polynomial has degree -1. """
cpdef list list(self, bint copy=True): """ Return a new copy of the list of the underlying elements of ``self``.
EXAMPLES::
sage: _.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: f = x^3 + 3*x - 17 sage: f.list() [83, 3, 0, 1] """
def ntl_set_directly(self, v): r""" Set the value of this polynomial directly from a vector or string.
Polynomials over the integers modulo n are stored internally using NTL's ``ZZ_pX`` class. Use this function to set the value of this polynomial using the NTL constructor, which is potentially *very* fast. The input v is either a vector of ints or a string of the form ``[ n1 n2 n3 ... ]`` where the ni are integers and there are no commas between them. The optimal input format is the string format, since that's what NTL uses by default.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n as poly_modn_dense sage: poly_modn_dense(R, ([1,-2,3])) 3*x^2 + 98*x + 1 sage: f = poly_modn_dense(R, 0) sage: f.ntl_set_directly([1,-2,3]) sage: f 3*x^2 + 98*x + 1 sage: f.ntl_set_directly('[1 -2 3 4]') sage: f 4*x^3 + 3*x^2 + 98*x + 1 """ raise TypeError("Cannot change the value of the generator.")
# Polynomial_singular_repr stuff, copied due to lack of multiple inheritance if not have_ring: self.parent()._singular_(singular,force=force).set_ring() # this is expensive if self.__singular is not None: try: self.__singular._check_valid() if self.__singular.parent() is singular: return self.__singular except (AttributeError, ValueError): pass return self._singular_init_(singular, have_ring=have_ring)
if not have_ring: self.parent()._singular_(singular,force=force).set_ring() # this is expensive self.__singular = singular(str(self)) return self.__singular
def small_roots(self, *args, **kwds): r""" See :func:`sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots` for the documentation of this function.
EXAMPLES::
sage: N = 10001 sage: K = Zmod(10001) sage: P.<x> = PolynomialRing(K, implementation='NTL') sage: f = x^3 + 10*x^2 + 5000*x - 222 sage: f.small_roots() [4] """
r""" Let `N` be the characteristic of the base ring this polynomial is defined over: ``N = self.base_ring().characteristic()``. This method returns small roots of this polynomial modulo some factor `b` of `N` with the constraint that `b >= N^\beta`. Small in this context means that if `x` is a root of `f` modulo `b` then `|x| < X`. This `X` is either provided by the user or the maximum `X` is chosen such that this algorithm terminates in polynomial time. If `X` is chosen automatically it is `X = ceil(1/2 N^{\beta^2/\delta - \epsilon})`. The algorithm may also return some roots which are larger than `X`. 'This algorithm' in this context means Coppersmith's algorithm for finding small roots using the LLL algorithm. The implementation of this algorithm follows Alexander May's PhD thesis referenced below.
INPUT:
- ``X`` -- an absolute bound for the root (default: see above) - ``beta`` -- compute a root mod `b` where `b` is a factor of `N` and `b \ge N^\beta`. (Default: 1.0, so `b = N`.) - ``epsilon`` -- the parameter `\epsilon` described above. (Default: `\beta/8`) - ``**kwds`` -- passed through to method :meth:`Matrix_integer_dense.LLL() <sage.matrix.matrix_integer_dense.Matrix_integer_dense.LLL>`.
EXAMPLES:
First consider a small example::
sage: N = 10001 sage: K = Zmod(10001) sage: P.<x> = PolynomialRing(K, implementation='NTL') sage: f = x^3 + 10*x^2 + 5000*x - 222
This polynomial has no roots without modular reduction (i.e. over `\ZZ`)::
sage: f.change_ring(ZZ).roots() []
To compute its roots we need to factor the modulus `N` and use the Chinese remainder theorem::
sage: p,q = N.prime_divisors() sage: f.change_ring(GF(p)).roots() [(4, 1)] sage: f.change_ring(GF(q)).roots() [(4, 1)]
sage: crt(4, 4, p, q) 4
This root is quite small compared to `N`, so we can attempt to recover it without factoring `N` using Coppersmith's small root method::
sage: f.small_roots() [4]
An application of this method is to consider RSA. We are using 512-bit RSA with public exponent `e=3` to encrypt a 56-bit DES key. Because it would be easy to attack this setting if no padding was used we pad the key `K` with 1s to get a large number::
sage: Nbits, Kbits = 512, 56 sage: e = 3
We choose two primes of size 256-bit each::
sage: p = 2^256 + 2^8 + 2^5 + 2^3 + 1 sage: q = 2^256 + 2^8 + 2^5 + 2^3 + 2^2 + 1 sage: N = p*q sage: ZmodN = Zmod( N )
We choose a random key::
sage: K = ZZ.random_element(0, 2^Kbits)
and pad it with 512-56=456 1s::
sage: Kdigits = K.digits(2) sage: M = [0]*Kbits + [1]*(Nbits-Kbits) sage: for i in range(len(Kdigits)): M[i] = Kdigits[i]
sage: M = ZZ(M, 2)
Now we encrypt the resulting message::
sage: C = ZmodN(M)^e
To recover `K` we consider the following polynomial modulo `N`::
sage: P.<x> = PolynomialRing(ZmodN, implementation='NTL') sage: f = (2^Nbits - 2^Kbits + x)^e - C
and recover its small roots::
sage: Kbar = f.small_roots()[0] sage: K == Kbar True
The same algorithm can be used to factor `N = pq` if partial knowledge about `q` is available. This example is from the Magma handbook:
First, we set up `p`, `q` and `N`::
sage: length = 512 sage: hidden = 110 sage: p = next_prime(2^int(round(length/2))) sage: q = next_prime( round(pi.n()*p) ) sage: N = p*q
Now we disturb the low 110 bits of `q`::
sage: qbar = q + ZZ.random_element(0,2^hidden-1)
And try to recover `q` from it::
sage: F.<x> = PolynomialRing(Zmod(N), implementation='NTL') sage: f = x - qbar
We know that the error is `\le 2^{\text{hidden}}-1` and that the modulus we are looking for is `\ge \sqrt{N}`::
sage: set_verbose(2) sage: d = f.small_roots(X=2^hidden-1, beta=0.5)[0] # time random verbose 2 (<module>) m = 4 verbose 2 (<module>) t = 4 verbose 2 (<module>) X = 1298074214633706907132624082305023 verbose 1 (<module>) LLL of 8x8 matrix (algorithm fpLLL:wrapper) verbose 1 (<module>) LLL finished (time = 0.006998) sage: q == qbar - d True
REFERENCES:
Don Coppersmith. *Finding a small root of a univariate modular equation.* In Advances in Cryptology, EuroCrypt 1996, volume 1070 of Lecture Notes in Computer Science, p. 155--165. Springer, 1996. http://cr.yp.to/bib/2001/coppersmith.pdf
Alexander May. *New RSA Vulnerabilities Using Lattice Reduction Methods.* PhD thesis, University of Paderborn, 2003. http://www.cs.uni-paderborn.de/uploads/tx_sibibtex/bp.pdf """
raise ArithmeticError("Polynomial must be monic.")
raise ValueError("0.0 < beta <= 1.0 not satisfied.")
# we could do this much faster, but this is a cheap step # compared to LLL
cdef class Polynomial_dense_modn_ntl_zz(Polynomial_dense_mod_n): r""" Polynomial on `\ZZ/n\ZZ` implemented via NTL.
.. automethod:: _add_ .. automethod:: _sub_ .. automethod:: _lmul_ .. automethod:: _rmul_ .. automethod:: _mul_ .. automethod:: _mul_trunc_ """ def __init__(self, parent, v=None, check=True, is_gen=False, construct=False): r""" EXAMPLES::
sage: R = Integers(5**21) sage: S.<x> = PolynomialRing(R, implementation='NTL') sage: S(1/4) 357627868652344 """ if (<Element>v)._parent == parent: Polynomial.__init__(self, parent, is_gen=is_gen) self.x = (<Polynomial_dense_modn_ntl_zz>v).x self.c = (<Polynomial_dense_modn_ntl_zz>v).c return
def __dealloc__(self):
def ntl_set_directly(self, v): # TODO: Get rid of this Polynomial_dense_mod_n.ntl_set_directly(self, v) # verbatim from __init__ v = [int(a) for a in self.__poly.list()] self.__poly = None # this will eventually go away cdef ntl_zz_pX ntl = ntl_zz_pX(v, self._parent.modulus()) # let it handle the hard work self.x = ntl.x self.c = ntl.c
cdef Polynomial_dense_modn_ntl_zz _new(self):
def int_list(self): """ Returns the coefficients of self as efficiently as possible as a list of python ints.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n as poly_modn_dense sage: f = poly_modn_dense(R,[5,0,0,1]) sage: f.int_list() [5, 0, 0, 1] sage: [type(a) for a in f.int_list()] [<... 'int'>, <... 'int'>, <... 'int'>, <... 'int'>] """ cdef long i return [ zz_p_rep(zz_pX_GetCoeff(self.x, i)) for i from 0 <= i <= zz_pX_deg(self.x) ]
cdef get_unsafe(self, Py_ssize_t n): """ Return the `n`-th coefficient of ``self``.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_modn_ntl_zz sage: f = Polynomial_dense_modn_ntl_zz(R,[2, 1])^7 sage: f[3] 60 sage: f[:6] 84*x^5 + 80*x^4 + 60*x^3 + 72*x^2 + 48*x + 28 sage: f[:50] == f True """
def _unsafe_mutate(self, n, value): self.c.restore_c() zz_pX_SetCoeff_long(self.x, n, value)
cpdef _add_(self, _right): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: (x+5) + (x^2 - 6) x^2 + x + 99 """
cpdef _sub_(self, _right): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: (x+5) - (x^2 - 6) 99*x^2 + x + 11 """
cpdef _mul_(self, _right): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: (x+5) * (x^2 - 1) x^3 + 5*x^2 + 99*x + 95 """ zz_pX_sqr(r.x, self.x) else:
cpdef Polynomial _mul_trunc_(self, Polynomial right, long n): r""" Return the product of ``self`` and ``right`` truncated to the given length `n`
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(100), implementation="NTL") sage: f = x - 2 sage: g = x^2 - 8*x + 16 sage: f*g x^3 + 90*x^2 + 32*x + 68 sage: f._mul_trunc_(g, 42) x^3 + 90*x^2 + 32*x + 68 sage: f._mul_trunc_(g, 3) 90*x^2 + 32*x + 68 sage: f._mul_trunc_(g, 2) 32*x + 68 sage: f._mul_trunc_(g, 1) 68 sage: f._mul_trunc_(g, 0) 0 sage: f = x^2 - 8*x + 16 sage: f._mul_trunc_(f, 2) 44*x + 56 """ else:
cpdef _rmul_(self, Element c): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: (x+5) * 3 3*x + 15 """
cpdef _lmul_(self, Element c): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: 3 * (x+5) 3*x + 15 """
def __pow__(Polynomial_dense_modn_ntl_zz self, ee, modulus): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: (x-1)^5 x^5 + 95*x^4 + 10*x^3 + 90*x^2 + 5*x + 99
Negative powers will not work::
sage: R.<x> = PolynomialRing(Integers(101), implementation='NTL') sage: (x-1)^(-5) Traceback (most recent call last): ... NotImplementedError: Fraction fields not implemented for this type.
We define ``0^0`` to be unity, :trac:`13895`::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: R(0)^0 1
The value returned from ``0^0`` should belong to our ring::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: type(R(0)^0) == type(R(0)) True
""" raise TypeError("Only integral powers defined.") recip = 1 e = -e
cdef zz_pX_Modulus_c *mod
else: else: if not isinstance(modulus, Polynomial_dense_modn_ntl_zz): modulus = self.parent()._coerce_(modulus) zz_pX_Modulus_build(mod[0], (<Polynomial_dense_modn_ntl_zz>modulus).x)
do_sig = zz_pX_deg(self.x) * e * self.c.p_bits > 1e5 if do_sig: sig_on() zz_pX_PowerMod_long_pre(r.x, self.x, e, mod[0]) if do_sig: sig_off()
return ~r else:
""" Returns `q` and `r`, with the degree of `r` less than the degree of `right`, such that `q * right + r = self`.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(125), implementation='NTL') sage: f = x^5+1; g = (x+1)^2 sage: q, r = f.quo_rem(g) sage: q x^3 + 123*x^2 + 3*x + 121 sage: r 5*x + 5 sage: q*g + r x^5 + 1 """
cpdef _floordiv_(self, right): """ Returns the whole part of self/right, without remainder.
For q = n // d, we have deg(n - q*d) < deg(d)
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(25), implementation='NTL') sage: f = x^7 + 1; g = x^2 - 1 sage: q = f // g; q x^5 + x^3 + x sage: f - q*g x + 1 """ cdef Polynomial_dense_modn_ntl_zz numer = <Polynomial_dense_modn_ntl_zz>self cdef Polynomial_dense_modn_ntl_zz denom = <Polynomial_dense_modn_ntl_zz>right cdef Polynomial_dense_modn_ntl_zz q = numer._new() sig_on() numer.c.restore_c() zz_pX_div(q.x, numer.x, denom.x) sig_off() return q
cpdef _mod_(self, right): """ EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(81), implementation='NTL') sage: f = x^7 + x + 1; g = x^3 sage: r = f % g; r x + 1 sage: g * x^4 + r x^7 + x + 1 """ cdef Polynomial_dense_modn_ntl_zz numer = <Polynomial_dense_modn_ntl_zz>self cdef Polynomial_dense_modn_ntl_zz denom = <Polynomial_dense_modn_ntl_zz>right cdef Polynomial_dense_modn_ntl_zz r = numer._new() sig_on() numer.c.restore_c() zz_pX_mod(r.x, numer.x, denom.x) sig_off() return r
def shift(self, n): """ Shift self to left by `n`, which is multiplication by `x^n`, truncating if `n` is negative.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^7 + x + 1 sage: f.shift(1) x^8 + x^2 + x sage: f.shift(-1) x^6 + 1 sage: f.shift(10).shift(-10) == f True
TESTS::
sage: p = R(0) sage: p.shift(3).is_zero() True sage: p.shift(-3).is_zero() True
"""
def __lshift__(Polynomial_dense_modn_ntl_zz self, long n): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^5 + 2*x + 1 sage: f << 3 x^8 + 2*x^4 + x^3 """
def __rshift__(Polynomial_dense_modn_ntl_zz self, long n): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^5 + 2*x + 1 sage: f >> 3 x^2 """
def _derivative(self, var=None): r""" Returns the formal derivative of self with respect to var.
var must be either the generator of the polynomial ring to which this polynomial belongs, or None (either way the behaviour is the same).
.. SEEALSO:: :meth:`.derivative`
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^4 - x - 1 sage: f._derivative() 4*x^3 + 76 sage: f._derivative(None) 4*x^3 + 76
sage: f._derivative(2*x) Traceback (most recent call last): ... ValueError: cannot differentiate with respect to 2*x
sage: y = var("y") sage: f._derivative(y) Traceback (most recent call last): ... ValueError: cannot differentiate with respect to y """
def reverse(self): """ Reverses the coefficients of self. The reverse of `f(x)` is `x^n f(1/x)`.
The degree will go down if the constant term is zero.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^4 - x - 1 sage: f.reverse() 76*x^4 + 76*x^3 + 1 sage: f = x^3 - x sage: f.reverse() 76*x^2 + 1 """
def is_gen(self):
def __nonzero__(self): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^4 - x - 1 sage: not f False sage: not (x-x) True """
def valuation(self): """ Returns the valuation of self, that is, the power of the lowest non-zero monomial of self.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10), implementation='NTL') sage: x.valuation() 1 sage: f = x-3; f.valuation() 0 sage: f = x^99; f.valuation() 99 sage: f = x-x; f.valuation() +Infinity """ cdef long n
def degree(self): """ EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = x^4 - x - 1 sage: f.degree() 4 sage: f = 77*x + 1 sage: f.degree() 0 """
cpdef Polynomial truncate(self, long n): """ Returns this polynomial mod `x^n`.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(77), implementation='NTL') sage: f = sum(x^n for n in range(10)); f x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 sage: f.truncate(6) x^5 + x^4 + x^3 + x^2 + x + 1 """
def __call__(self, *args, **kwds): """ Evaluate self at x. If x is a single argument coercible into the base ring of self, this is done directly in NTL, otherwise the generic Polynomial call code is used.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL') sage: f = x^3+7 sage: f(5) 32 sage: f(5r) 32 sage: f(mod(5, 1000)) 32 sage: f(x) x^3 + 7 sage: S.<y> = PolynomialRing(Integers(5), implementation='NTL') sage: f(y) y^3 + 2 """ return Polynomial.__call__(self, *args, **kwds) else: else:
cdef class Polynomial_dense_modn_ntl_ZZ(Polynomial_dense_mod_n):
def __init__(self, parent, v=None, check=True, is_gen=False, construct=False): Polynomial.__init__(self, parent, is_gen=is_gen) self.x = (<Polynomial_dense_modn_ntl_ZZ>v).x self.c = (<Polynomial_dense_modn_ntl_ZZ>v).c return
def __dealloc__(self):
cdef Polynomial_dense_modn_ntl_ZZ _new(self):
cpdef list list(self, bint copy=True):
cdef get_unsafe(self, Py_ssize_t n): """ Return the `n`-th coefficient of ``self``.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_modn_ntl_ZZ sage: f = Polynomial_dense_modn_ntl_ZZ(R,[2,1])^7 sage: f[3] 560 sage: f[:6] 84*x^5 + 280*x^4 + 560*x^3 + 672*x^2 + 448*x + 128 sage: f[:50] == f True """ # TODO, make this faster
def _unsafe_mutate(self, n, value): self.c.restore_c() cdef Integer a if isinstance(value, Integer): a = <Integer>value else: a = ZZ(value) cdef ntl_ZZ_p val = ntl_ZZ_p(a, self.c) ZZ_pX_SetCoeff(self.x, n, val.x)
cpdef _add_(self, _right): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: (x+5) + (x^2 - 6) x^2 + x + 999999999999999999999999999999 """
cpdef _sub_(self, _right): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: (x+5) - (x^2 - 6) 999999999999999999999999999999*x^2 + x + 11 """
cpdef _mul_(self, _right): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: (x+5) * (x^2 - 1) x^3 + 5*x^2 + 999999999999999999999999999999*x + 999999999999999999999999999995 """ else:
cpdef Polynomial _mul_trunc_(self, Polynomial right, long n): """ Return the product of ``self`` and ``right`` truncated to the given length `n`, only return terms of degree less than `n`.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation="NTL") sage: f = x - 2 sage: g = x^2 - 8*x + 16 sage: f*g x^3 + 999999999999999999999999999990*x^2 + 32*x + 999999999999999999999999999968 sage: f._mul_trunc_(g, 42) x^3 + 999999999999999999999999999990*x^2 + 32*x + 999999999999999999999999999968 sage: f._mul_trunc_(g, 3) 999999999999999999999999999990*x^2 + 32*x + 999999999999999999999999999968 sage: f._mul_trunc_(g, 2) 32*x + 999999999999999999999999999968 sage: f._mul_trunc_(g, 1) 999999999999999999999999999968 sage: f._mul_trunc_(g, 0) 0 sage: f = x^2 - 8*x + 16 sage: f._mul_trunc_(f, 2) 999999999999999999999999999744*x + 256 """ else:
cpdef _rmul_(self, Element c): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: (x+5) * 3 3*x + 15 """
cpdef _lmul_(self, Element c): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: 3 * (x+5) 3*x + 15 """
def __pow__(Polynomial_dense_modn_ntl_ZZ self, ee, modulus): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: (x+1)^5 x^5 + 5*x^4 + 10*x^3 + 10*x^2 + 5*x + 1
We define ``0^0`` to be unity, :trac:`13895`::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: R(0)^0 1
The value returned from ``0^0`` should belong to our ring::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: type(R(0)^0) == type(R(0)) True
""" raise TypeError("Only integral powers defined.") recip = 1 # delay because powering frac field elements is slow e = -e cdef ZZ_pX_Modulus_c *mod
else: else: if not isinstance(modulus, Polynomial_dense_modn_ntl_ZZ): modulus = self.parent()._coerce_(modulus) ZZ_pX_Modulus_build(mod[0], (<Polynomial_dense_modn_ntl_ZZ>modulus).x)
do_sig = ZZ_pX_deg(self.x) * e * self.c.p_bits > 1e5 if do_sig: sig_on() ZZ_pX_PowerMod_long_pre(r.x, self.x, e, mod[0]) if do_sig: sig_off() return ~r else:
""" Returns `q` and `r`, with the degree of `r` less than the degree of `right`, such that `q * right + r = self`.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: f = x^5+1; g = (x+1)^2 sage: q, r = f.quo_rem(g) sage: q x^3 + 999999999999999999999999999998*x^2 + 3*x + 999999999999999999999999999996 sage: r 5*x + 5 sage: q*g + r x^5 + 1 """
cpdef _floordiv_(self, right): """ Returns the whole part of self/right, without remainder.
For q = n // d, we have deg(n - q*d) < deg(d)
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: f = x^7 + 1; g = x^2 - 1 sage: q = f // g; q x^5 + x^3 + x sage: f - q*g x + 1 """ cdef Polynomial_dense_modn_ntl_ZZ numer = <Polynomial_dense_modn_ntl_ZZ>self cdef Polynomial_dense_modn_ntl_ZZ denom = <Polynomial_dense_modn_ntl_ZZ>right cdef Polynomial_dense_modn_ntl_ZZ q = numer._new() sig_on() numer.c.restore_c() ZZ_pX_div(q.x, numer.x, denom.x) sig_off() return q
cpdef _mod_(self, right): """ EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(9^30), implementation='NTL') sage: f = x^7 + x + 1; g = x^3 - 1 sage: r = f % g; r 2*x + 1 sage: g * (x^4 + x) + r x^7 + x + 1 """ cdef Polynomial_dense_modn_ntl_ZZ numer = <Polynomial_dense_modn_ntl_ZZ>self cdef Polynomial_dense_modn_ntl_ZZ denom = <Polynomial_dense_modn_ntl_ZZ>right cdef Polynomial_dense_modn_ntl_ZZ r = numer._new() sig_on() numer.c.restore_c() ZZ_pX_rem(r.x, numer.x, denom.x) sig_off() return r
def shift(self, n): """ Shift self to left by `n`, which is multiplication by `x^n`, truncating if `n` is negative.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(12^30), implementation='NTL') sage: f = x^7 + x + 1 sage: f.shift(1) x^8 + x^2 + x sage: f.shift(-1) x^6 + 1 sage: f.shift(10).shift(-10) == f True
TESTS::
sage: p = R(0) sage: p.shift(3).is_zero() True sage: p.shift(-3).is_zero() True
"""
def __lshift__(Polynomial_dense_modn_ntl_ZZ self, long n): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(14^30), implementation='NTL') sage: f = x^5 + 2*x + 1 sage: f << 3 x^8 + 2*x^4 + x^3 """
def __rshift__(Polynomial_dense_modn_ntl_ZZ self, long n): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(15^30), implementation='NTL') sage: f = x^5 + 2*x + 1 sage: f >> 3 x^2 """
def _derivative(self, var=None): r""" Returns the formal derivative of self with respect to var.
var must be either the generator of the polynomial ring to which this polynomial belongs, or None (either way the behaviour is the same).
.. SEEALSO:: :meth:`.derivative`
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(12^29), implementation='NTL') sage: f = x^4 + x + 5 sage: f._derivative() 4*x^3 + 1 sage: f._derivative(None) 4*x^3 + 1
sage: f._derivative(2*x) Traceback (most recent call last): ... ValueError: cannot differentiate with respect to 2*x
sage: y = var("y") sage: f._derivative(y) Traceback (most recent call last): ... ValueError: cannot differentiate with respect to y """
def reverse(self): """ Reverses the coefficients of self. The reverse of `f(x)` is `x^n f(1/x)`.
The degree will go down if the constant term is zero.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(12^29), implementation='NTL') sage: f = x^4 + 2*x + 5 sage: f.reverse() 5*x^4 + 2*x^3 + 1 sage: f = x^3 + x sage: f.reverse() x^2 + 1 """
def is_gen(self):
def valuation(self): """ Returns the valuation of self, that is, the power of the lowest non-zero monomial of self.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10^50), implementation='NTL') sage: x.valuation() 1 sage: f = x-3; f.valuation() 0 sage: f = x^99; f.valuation() 99 sage: f = x-x; f.valuation() +Infinity """ cdef long n cdef ZZ_p_c coeff
def __nonzero__(self): """ TESTS::
sage: R.<x> = PolynomialRing(Integers(12^29), implementation='NTL') sage: f = x^4 + 1 sage: not f False sage: not (x-x) True """
def degree(self): """ EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(14^34), implementation='NTL') sage: f = x^4 - x - 1 sage: f.degree() 4 sage: f = 14^43*x + 1 sage: f.degree() 0 """
cpdef Polynomial truncate(self, long n): """ Returns this polynomial mod `x^n`.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(15^30), implementation='NTL') sage: f = sum(x^n for n in range(10)); f x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 sage: f.truncate(6) x^5 + x^4 + x^3 + x^2 + x + 1 """
def __call__(self, *args, **kwds): """ Evaluate self at x. If x is a single argument coercible into the base ring of self, this is done directly in NTL, otherwise the generic Polynomial call code is used.
EXAMPLES::
sage: R.<x> = PolynomialRing(Integers(10^30), implementation='NTL') sage: f = x^3+7 sage: f(5) 132 sage: f(5r) 132 sage: f(mod(5, 10^50)) 132 sage: f(x) x^3 + 7 sage: S.<y> = PolynomialRing(Integers(5), implementation='NTL') sage: f(y) y^3 + 2 """ return Polynomial.__call__(self, *args, **kwds) else: else:
cdef class Polynomial_dense_mod_p(Polynomial_dense_mod_n): """ A dense polynomial over the integers modulo p, where p is prime. """
""" Return the greatest common divisor of this polynomial and ``other``, as a monic polynomial.
INPUT:
- ``other`` -- a polynomial defined over the same ring as ``self``
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(3),implementation="NTL") sage: f,g = x + 2, x^2 - 1 sage: f.gcd(g) x + 2
"""
r""" Compute the extended gcd of this element and ``other``.
INPUT:
- ``other`` -- an element in the same polynomial ring
OUTPUT:
A tuple ``(r,s,t)`` of elements in the polynomial ring such that ``r = s*self + t*other``.
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(3),implementation='NTL') sage: x.xgcd(x) (x, 0, 1) sage: (x^2 - 1).xgcd(x - 1) (x + 2, 0, 1) sage: R.zero().xgcd(R.one()) (1, 0, 1) sage: (x^3 - 1).xgcd((x - 1)^2) (x^2 + x + 1, 0, 1) sage: ((x - 1)*(x + 1)).xgcd(x*(x - 1)) (x + 2, 1, 2)
"""
""" Returns the resultant of self and other, which must lie in the same polynomial ring.
INPUT:
- ``other`` -- a polynomial
OUTPUT: an element of the base ring of the polynomial ring
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(19),implementation='NTL') sage: f = x^3 + x + 1; g = x^3 - x - 1 sage: r = f.resultant(g); r 11 sage: r.parent() is GF(19) True """
def discriminant(self): """ EXAMPLES::
sage: _.<x> = PolynomialRing(GF(19),implementation='NTL') sage: f = x^3 + 3*x - 17 sage: f.discriminant() 12 """ |