Dense univariate polynomials over $Z / n Z$ , implemented using NTL#

This implementation is generally slower than the FLINT implementation in 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 Polynomial_dense_modn_ntl_zz and 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)

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_n#

Bases: 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

degree(gen=None)#

Return the degree of this polynomial.

The zero polynomial has degree -1.

EXAMPLES:

sage: R.<x> = PolynomialRing(Integers(100), implementation='NTL')
sage: (x^3 + 3*x - 17).degree()
3
sage: R.zero().degree()
-1

int_list()#

list(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]

ntl_ZZ_pX()#: 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!

ntl_set_directly(v)#

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

quo_rem(right)#: Returns a tuple (quotient, remainder) where self = quotient*other + remainder.

shift(n)#

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

AUTHOR:

David Harvey (2006-08-06)

small_roots(*args, **kwds)#

See 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]

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p#

Bases: Polynomial_dense_mod_n

A dense polynomial over the integers modulo p, where p is prime.

discriminant()#

EXAMPLES:

sage: _.<x> = PolynomialRing(GF(19),implementation='NTL')
sage: f = x^3 + 3*x - 17
sage: f.discriminant()
12

gcd(right)#

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

resultant(other)#

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

xgcd(other)#

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)

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_ZZ#

Bases: Polynomial_dense_mod_n

degree()#

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

is_gen()#

list(copy=True)#

quo_rem(right)#

Returns $q$ and $r$ , with the degree of $r$ less than the degree of $r i g h t$ , such that $q * r i g h t + r = s e l f$ .

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

reverse(degree=None)#

Return the reverse of the input polynomial thought as a polynomial of degree degree.

If $f$ is a degree- $d$ polynomial, its reverse is $x^{d} f (1 / x)$ .

INPUT:

degree (None or an integer) - if specified, truncate or zero pad the list of coefficients to this degree before reversing it.

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
sage: f.reverse(1)
1
sage: f.reverse(5)
x^4 + x^2

shift(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

truncate(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

valuation()#

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

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_zz#

Bases: Polynomial_dense_mod_n

Polynomial on $Z / n Z$ implemented via NTL.

_add_(_right)#

_sub_(_right)#

_lmul_(c)#

_rmul_(c)#

_mul_(_right)#

_mul_trunc_(right, n)#

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

degree()#

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

int_list()#

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'>]

is_gen()#

ntl_set_directly(v)#

quo_rem(right)#

Returns $q$ and $r$ , with the degree of $r$ less than the degree of $r i g h t$ , such that $q * r i g h t + r = s e l f$ .

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

reverse(degree=None)#

Return the reverse of the input polynomial thought as a polynomial of degree degree.

If $f$ is a degree- $d$ polynomial, its reverse is $x^{d} f (1 / x)$ .

INPUT:

degree (None or an integer) - if specified, truncate or zero pad the list of coefficients to this degree before reversing it.

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.reverse(2)
76*x^2 + 76*x
sage: f.reverse(5)
76*x^5 + 76*x^4 + x
sage: g = x^3 - x
sage: g.reverse()
76*x^2 + 1

shift(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

truncate(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

valuation()#

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

sage.rings.polynomial.polynomial_modn_dense_ntl.make_element(parent, args)#

sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots(self, X=None, beta=1.0, epsilon=None, **kwds)#

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^{β}$ . 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 = c e i l (1 / 2 N^{β^{2} / δ - ϵ})$ . 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 \geq N^{β}$ . (Default: 1.0, so $b = N$ .)
epsilon – the parameter $ϵ$ described above. (Default: $β / 8$ )
**kwds – passed through to method 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 $Z$ ):

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 = p q$ 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 $\leq 2^{hidden} - 1$ and that the modulus we are looking for is $\geq \sqrt{N}$ :

sage: from sage.misc.verbose import set_verbose
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

Dense univariate polynomials over Z/nZ, implemented using NTL#

Dense univariate polynomials over $Z / n Z$ , implemented using NTL#