Dense univariate polynomials over $$\ZZ/n\ZZ$$, implemented using NTL.¶

Dense univariate polynomials over $$\ZZ/n\ZZ$$, 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

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

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.

int_list()
list()

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


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)
small_roots(*args, **kwds)

See sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots() for the documentation of this function.

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
sage: f.small_roots()
[4]

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p

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
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()
quo_rem(right)

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

reverse()

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

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


TESTS:

sage: p = R(0)
sage: p.shift(3).is_zero()
True
sage: p.shift(-3).is_zero()
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

EXAMPLES:

sage: R = Integers(5**21)
sage: S.<x> = PolynomialRing(R, implementation='NTL')
sage: S(1/4)
357627868652344

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()]
[<type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>]

is_gen()
ntl_set_directly(v)
quo_rem(right)

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

reverse()

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

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


TESTS:

sage: p = R(0)
sage: p.shift(3).is_zero()
True
sage: p.shift(-3).is_zero()
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^\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 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

Dense univariate polynomials over $$\ZZ/n\ZZ$$, implemented using FLINT.
Dense univariate polynomials over $$\RR$$, implemented using MPFR