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[source]¶

Bases: Polynomial

A dense polynomial over the integers modulo n, where n is composite, with the underlying arithmetic done using NTL.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(16)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - x + Integer(17)
>>> f**Integer(2)
x^6 + 14*x^4 + 2*x^3 + x^2 + 14*x + 1

>>> loads(f.dumps()) == f
True

>>> R = PolynomialRing(Integers(Integer(100)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> p = Integer(3)*x
>>> q = Integer(7)*x
>>> p + q
10*x
>>> R = PolynomialRing(Integers(Integer(8)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> parent(p)
Univariate Polynomial Ring in x over Ring of integers modulo 100 (using NTL)
>>> p + q
10*x
>>> R({Integer(10):-Integer(1)})
7*x^10

Sage Live

R.<x> = PolynomialRing(Integers(16), implementation='NTL')
f = x^3 - x + 17
f^2
loads(f.dumps()) == f
R.<x> = PolynomialRing(Integers(100), implementation='NTL')
p = 3*x
q = 7*x
p + q
R.<x> = PolynomialRing(Integers(8), implementation='NTL')
parent(p)
p + q
R({10:-1})

compose_mod(other, modulus)[source]¶

Compute $f (g) (\mod h)$ .

To be precise about the order fo compostion, given self, other and modulus as $f (x)$ , $g (x)$ and $h (x)$ compute $f (g (x)) mod h (x)$ .

INPUT:

other – a polynomial $g (x)$
modulus – a polynomial $h (x)$

EXAMPLES:

Sage

sage: R.<x> = GF(2**127 - 1)[]
sage: f = R.random_element()
sage: g = R.random_element()
sage: g.compose_mod(g, f) == g(g) % f
True

sage: R.<x> = GF(163)[]
sage: f = R([i for i in range(100)])
sage: g = R([i**2 for i in range(100)])
sage: h = 1 + x + x**5
sage: f.compose_mod(g, h)
82*x^4 + 56*x^3 + 45*x^2 + 60*x + 127
sage: f.compose_mod(g, h) == f(g) % h
True

Python

>>> from sage.all import *
>>> R = GF(Integer(2)**Integer(127) - Integer(1))['x']; (x,) = R._first_ngens(1)
>>> f = R.random_element()
>>> g = R.random_element()
>>> g.compose_mod(g, f) == g(g) % f
True

>>> R = GF(Integer(163))['x']; (x,) = R._first_ngens(1)
>>> f = R([i for i in range(Integer(100))])
>>> g = R([i**Integer(2) for i in range(Integer(100))])
>>> h = Integer(1) + x + x**Integer(5)
>>> f.compose_mod(g, h)
82*x^4 + 56*x^3 + 45*x^2 + 60*x + 127
>>> f.compose_mod(g, h) == f(g) % h
True

Sage Live

R.<x> = GF(2**127 - 1)[]
f = R.random_element()
g = R.random_element()
g.compose_mod(g, f) == g(g) % f
R.<x> = GF(163)[]
f = R([i for i in range(100)])
g = R([i**2 for i in range(100)])
h = 1 + x + x**5
f.compose_mod(g, h)
f.compose_mod(g, h) == f(g) % h

AUTHORS:

Giacomo Pope (2024-08) initial implementation

degree(gen=None)[source]¶

Return the degree of this polynomial.

The zero polynomial has degree -1.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(100)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> (x**Integer(3) + Integer(3)*x - Integer(17)).degree()
3
>>> R.zero().degree()
-1

Sage Live

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

int_list()[source]¶

list(copy=True)[source]¶

Return a new copy of the list of the underlying elements of self.

EXAMPLES:

Sage

sage: _.<x> = PolynomialRing(Integers(100), implementation='NTL')
sage: f = x^3 + 3*x - 17
sage: f.list()
[83, 3, 0, 1]

Python

>>> from sage.all import *
>>> _ = PolynomialRing(Integers(Integer(100)), implementation='NTL', names=('x',)); (x,) = _._first_ngens(1)
>>> f = x**Integer(3) + Integer(3)*x - Integer(17)
>>> f.list()
[83, 3, 0, 1]

Sage Live

_.<x> = PolynomialRing(Integers(100), implementation='NTL')
f = x^3 + 3*x - 17
f.list()

minpoly_mod(other)[source]¶

Compute the minimal polynomial of this polynomial modulo another polynomial in the same ring.

ALGORITHM:

NTL’s MinPolyMod(), which uses Shoup’s algorithm [Sho1999].

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(GF(101), implementation='NTL')
sage: f = x^17 + x^2 - 1
sage: (x^2).minpoly_mod(f)
x^17 + 100*x^2 + 2*x + 100

Python

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(101)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(17) + x**Integer(2) - Integer(1)
>>> (x**Integer(2)).minpoly_mod(f)
x^17 + 100*x^2 + 2*x + 100

Sage Live

R.<x> = PolynomialRing(GF(101), implementation='NTL')
f = x^17 + x^2 - 1
(x^2).minpoly_mod(f)

modular_composition(other, modulus)[source]¶

Compute $f (g) (\mod h)$ .

To be precise about the order fo compostion, given self, other and modulus as $f (x)$ , $g (x)$ and $h (x)$ compute $f (g (x)) mod h (x)$ .

INPUT:

other – a polynomial $g (x)$
modulus – a polynomial $h (x)$

EXAMPLES:

Sage

sage: R.<x> = GF(2**127 - 1)[]
sage: f = R.random_element()
sage: g = R.random_element()
sage: g.compose_mod(g, f) == g(g) % f
True

sage: R.<x> = GF(163)[]
sage: f = R([i for i in range(100)])
sage: g = R([i**2 for i in range(100)])
sage: h = 1 + x + x**5
sage: f.compose_mod(g, h)
82*x^4 + 56*x^3 + 45*x^2 + 60*x + 127
sage: f.compose_mod(g, h) == f(g) % h
True

Python

>>> from sage.all import *
>>> R = GF(Integer(2)**Integer(127) - Integer(1))['x']; (x,) = R._first_ngens(1)
>>> f = R.random_element()
>>> g = R.random_element()
>>> g.compose_mod(g, f) == g(g) % f
True

>>> R = GF(Integer(163))['x']; (x,) = R._first_ngens(1)
>>> f = R([i for i in range(Integer(100))])
>>> g = R([i**Integer(2) for i in range(Integer(100))])
>>> h = Integer(1) + x + x**Integer(5)
>>> f.compose_mod(g, h)
82*x^4 + 56*x^3 + 45*x^2 + 60*x + 127
>>> f.compose_mod(g, h) == f(g) % h
True

Sage Live

R.<x> = GF(2**127 - 1)[]
f = R.random_element()
g = R.random_element()
g.compose_mod(g, f) == g(g) % f
R.<x> = GF(163)[]
f = R([i for i in range(100)])
g = R([i**2 for i in range(100)])
h = 1 + x + x**5
f.compose_mod(g, h)
f.compose_mod(g, h) == f(g) % h

AUTHORS:

Giacomo Pope (2024-08) initial implementation

ntl_ZZ_pX()[source]¶: 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)[source]¶

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

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(100)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n as poly_modn_dense
>>> poly_modn_dense(R, ([Integer(1),-Integer(2),Integer(3)]))
3*x^2 + 98*x + 1
>>> f = poly_modn_dense(R, Integer(0))
>>> f.ntl_set_directly([Integer(1),-Integer(2),Integer(3)])
>>> f
3*x^2 + 98*x + 1
>>> f.ntl_set_directly('[1 -2 3 4]')
>>> f
4*x^3 + 3*x^2 + 98*x + 1

Sage Live

R.<x> = PolynomialRing(Integers(100), implementation='NTL')
from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n as poly_modn_dense
poly_modn_dense(R, ([1,-2,3]))
f = poly_modn_dense(R, 0)
f.ntl_set_directly([1,-2,3])
f
f.ntl_set_directly('[1 -2 3 4]')
f

quo_rem(right)[source]¶: Return a tuple (quotient, remainder) where self = quotient*other + remainder.

shift(n)[source]¶

Return 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

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(12345678901234567890)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> p = x**Integer(2) + Integer(2)*x + Integer(4)
>>> p.shift(Integer(0))
 x^2 + 2*x + 4
>>> p.shift(-Integer(1))
 x + 2
>>> p.shift(-Integer(5))
 0
>>> p.shift(Integer(2))
 x^4 + 2*x^3 + 4*x^2

Sage Live

R.<x> = PolynomialRing(Integers(12345678901234567890), implementation='NTL')
p = x^2 + 2*x + 4
p.shift(0)
p.shift(-1)
p.shift(-5)
p.shift(2)

AUTHOR:

David Harvey (2006-08-06)

small_roots(*args, **kwds)[source]¶

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

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> N = Integer(10001)
>>> K = Zmod(Integer(10001))
>>> P = PolynomialRing(K, implementation='NTL', names=('x',)); (x,) = P._first_ngens(1)
>>> f = x**Integer(3) + Integer(10)*x**Integer(2) + Integer(5000)*x - Integer(222)
>>> f.small_roots()
[4]

Sage Live

N = 10001
K = Zmod(10001)
P.<x> = PolynomialRing(K, implementation='NTL')
f = x^3 + 10*x^2 + 5000*x - 222
f.small_roots()

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p[source]¶

Bases: Polynomial_dense_mod_n

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

discriminant()[source]¶

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> _ = PolynomialRing(GF(Integer(19)), implementation='NTL', names=('x',)); (x,) = _._first_ngens(1)
>>> f = x**Integer(3) + Integer(3)*x - Integer(17)
>>> f.discriminant()
12

Sage Live

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

gcd(right)[source]¶

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

sage: R.<x> = PolynomialRing(GF(3), implementation="NTL")
sage: f, g = x + 2, x^2 - 1
sage: f.gcd(g)
x + 2

Python

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(3)), implementation="NTL", names=('x',)); (x,) = R._first_ngens(1)
>>> f, g = x + Integer(2), x**Integer(2) - Integer(1)
>>> f.gcd(g)
x + 2

Sage Live

R.<x> = PolynomialRing(GF(3), implementation="NTL")
f, g = x + 2, x^2 - 1
f.gcd(g)

resultant(other)[source]¶

Return 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

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(19)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(3) + x + Integer(1);  g = x**Integer(3) - x - Integer(1)
>>> r = f.resultant(g); r
11
>>> r.parent() is GF(Integer(19))
True

Sage Live

R.<x> = PolynomialRing(GF(19), implementation='NTL')
f = x^3 + x + 1;  g = x^3 - x - 1
r = f.resultant(g); r
r.parent() is GF(19)

xgcd(other)[source]¶

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

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)

Python

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(3)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> x.xgcd(x)
(x, 0, 1)
>>> (x**Integer(2) - Integer(1)).xgcd(x - Integer(1))
(x + 2, 0, 1)
>>> R.zero().xgcd(R.one())
(1, 0, 1)
>>> (x**Integer(3) - Integer(1)).xgcd((x - Integer(1))**Integer(2))
(x^2 + x + 1, 0, 1)
>>> ((x - Integer(1))*(x + Integer(1))).xgcd(x*(x - Integer(1)))
(x + 2, 1, 2)

Sage Live

R.<x> = PolynomialRing(GF(3), implementation='NTL')
x.xgcd(x)
(x^2 - 1).xgcd(x - 1)
R.zero().xgcd(R.one())
(x^3 - 1).xgcd((x - 1)^2)
((x - 1)*(x + 1)).xgcd(x*(x - 1))

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_ZZ[source]¶

Bases: Polynomial_dense_mod_n

degree()[source]¶

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(14)**Integer(34)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - x - Integer(1)
>>> f.degree()
4
>>> f = Integer(14)**Integer(43)*x + Integer(1)
>>> f.degree()
0

Sage Live

R.<x> = PolynomialRing(Integers(14^34), implementation='NTL')
f = x^4 - x - 1
f.degree()
f = 14^43*x + 1
f.degree()

is_gen()[source]¶

list(copy=True)[source]¶

quo_rem(right)[source]¶

Return $q$ and $r$ , with the degree of $r$ less than the degree of right, such that $q \cdot$ right $+ r =$ self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(10)**Integer(30)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(5)+Integer(1); g = (x+Integer(1))**Integer(2)
>>> q, r = f.quo_rem(g)
>>> q
x^3 + 999999999999999999999999999998*x^2 + 3*x + 999999999999999999999999999996
>>> r
5*x + 5
>>> q*g + r
x^5 + 1

Sage Live

R.<x> = PolynomialRing(Integers(10^30), implementation='NTL')
f = x^5+1; g = (x+1)^2
q, r = f.quo_rem(g)
q
r
q*g + r

reverse(degree=None)[source]¶

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 integer; if specified, truncate or zero pad the list of coefficients to this degree before reversing it

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(12)**Integer(29)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(4) + Integer(2)*x + Integer(5)
>>> f.reverse()
5*x^4 + 2*x^3 + 1
>>> f = x**Integer(3) + x
>>> f.reverse()
x^2 + 1
>>> f.reverse(Integer(1))
1
>>> f.reverse(Integer(5))
x^4 + x^2

Sage Live

R.<x> = PolynomialRing(Integers(12^29), implementation='NTL')
f = x^4 + 2*x + 5
f.reverse()
f = x^3 + x
f.reverse()
f.reverse(1)
f.reverse(5)

shift(n)[source]¶

Shift self to left by $n$ , which is multiplication by $x^{n}$ , truncating if $n$ is negative.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(12)**Integer(30)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(7) + x + Integer(1)
>>> f.shift(Integer(1))
x^8 + x^2 + x
>>> f.shift(-Integer(1))
x^6 + 1
>>> f.shift(Integer(10)).shift(-Integer(10)) == f
True

Sage Live

R.<x> = PolynomialRing(Integers(12^30), implementation='NTL')
f = x^7 + x + 1
f.shift(1)
f.shift(-1)
f.shift(10).shift(-10) == f

truncate(n)[source]¶

Return this polynomial mod $x^{n}$ .

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(15)**Integer(30)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = sum(x**n for n in range(Integer(10))); f
x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
>>> f.truncate(Integer(6))
x^5 + x^4 + x^3 + x^2 + x + 1

Sage Live

R.<x> = PolynomialRing(Integers(15^30), implementation='NTL')
f = sum(x^n for n in range(10)); f
f.truncate(6)

valuation()[source]¶

Return the valuation of self, that is, the power of the lowest nonzero monomial of self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(10)**Integer(50)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> x.valuation()
1
>>> f = x - Integer(3); f.valuation()
0
>>> f = x**Integer(99); f.valuation()
99
>>> f = x - x; f.valuation()
+Infinity

Sage Live

R.<x> = PolynomialRing(Integers(10^50), implementation='NTL')
x.valuation()
f = x - 3; f.valuation()
f = x^99; f.valuation()
f = x - x; f.valuation()

class sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_zz[source]¶

Bases: Polynomial_dense_mod_n

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

_add_(_right)[source]¶

_sub_(_right)[source]¶

_lmul_(c)[source]¶

_rmul_(c)[source]¶

_mul_(_right)[source]¶

_mul_trunc_(right, n)[source]¶

Return the product of self and right truncated to the given length $n$

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(100)), implementation="NTL", names=('x',)); (x,) = R._first_ngens(1)
>>> f = x - Integer(2)
>>> g = x**Integer(2) - Integer(8)*x + Integer(16)
>>> f*g
x^3 + 90*x^2 + 32*x + 68
>>> f._mul_trunc_(g, Integer(42))
x^3 + 90*x^2 + 32*x + 68
>>> f._mul_trunc_(g, Integer(3))
90*x^2 + 32*x + 68
>>> f._mul_trunc_(g, Integer(2))
32*x + 68
>>> f._mul_trunc_(g, Integer(1))
68
>>> f._mul_trunc_(g, Integer(0))
0
>>> f = x**Integer(2) - Integer(8)*x + Integer(16)
>>> f._mul_trunc_(f, Integer(2))
44*x + 56

Sage Live

R.<x> = PolynomialRing(Integers(100), implementation="NTL")
f = x - 2
g = x^2 - 8*x + 16
f*g
f._mul_trunc_(g, 42)
f._mul_trunc_(g, 3)
f._mul_trunc_(g, 2)
f._mul_trunc_(g, 1)
f._mul_trunc_(g, 0)
f = x^2 - 8*x + 16
f._mul_trunc_(f, 2)

degree()[source]¶

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(77)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - x - Integer(1)
>>> f.degree()
4
>>> f = Integer(77)*x + Integer(1)
>>> f.degree()
0

Sage Live

R.<x> = PolynomialRing(Integers(77), implementation='NTL')
f = x^4 - x - 1
f.degree()
f = 77*x + 1
f.degree()

int_list()[source]¶

Return the coefficients of self as efficiently as possible as a list of python ints.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(100)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n as poly_modn_dense
>>> f = poly_modn_dense(R,[Integer(5),Integer(0),Integer(0),Integer(1)])
>>> f.int_list()
[5, 0, 0, 1]
>>> [type(a) for a in f.int_list()]
[<... 'int'>, <... 'int'>, <... 'int'>, <... 'int'>]

Sage Live

R.<x> = PolynomialRing(Integers(100), implementation='NTL')
from sage.rings.polynomial.polynomial_modn_dense_ntl import Polynomial_dense_mod_n as poly_modn_dense
f = poly_modn_dense(R,[5,0,0,1])
f.int_list()
[type(a) for a in f.int_list()]

is_gen()[source]¶

ntl_set_directly(v)[source]¶

quo_rem(right)[source]¶

Return $q$ and $r$ , with the degree of $r$ less than the degree of right, such that $q \cdot$ right $+ r =$ self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(125)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(5)+Integer(1); g = (x+Integer(1))**Integer(2)
>>> q, r = f.quo_rem(g)
>>> q
x^3 + 123*x^2 + 3*x + 121
>>> r
5*x + 5
>>> q*g + r
x^5 + 1

Sage Live

R.<x> = PolynomialRing(Integers(125), implementation='NTL')
f = x^5+1; g = (x+1)^2
q, r = f.quo_rem(g)
q
r
q*g + r

reverse(degree=None)[source]¶

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 integer; if specified, truncate or zero pad the list of coefficients to this degree before reversing it

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(77)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - x - Integer(1)
>>> f.reverse()
76*x^4 + 76*x^3 + 1
>>> f.reverse(Integer(2))
76*x^2 + 76*x
>>> f.reverse(Integer(5))
76*x^5 + 76*x^4 + x
>>> g = x**Integer(3) - x
>>> g.reverse()
76*x^2 + 1

Sage Live

R.<x> = PolynomialRing(Integers(77), implementation='NTL')
f = x^4 - x - 1
f.reverse()
f.reverse(2)
f.reverse(5)
g = x^3 - x
g.reverse()

shift(n)[source]¶

Shift self to left by $n$ , which is multiplication by $x^{n}$ , truncating if $n$ is negative.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(77)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(7) + x + Integer(1)
>>> f.shift(Integer(1))
x^8 + x^2 + x
>>> f.shift(-Integer(1))
x^6 + 1
>>> f.shift(Integer(10)).shift(-Integer(10)) == f
True

Sage Live

R.<x> = PolynomialRing(Integers(77), implementation='NTL')
f = x^7 + x + 1
f.shift(1)
f.shift(-1)
f.shift(10).shift(-10) == f

truncate(n)[source]¶

Return this polynomial mod $x^{n}$ .

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(77)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = sum(x**n for n in range(Integer(10))); f
x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
>>> f.truncate(Integer(6))
x^5 + x^4 + x^3 + x^2 + x + 1

Sage Live

R.<x> = PolynomialRing(Integers(77), implementation='NTL')
f = sum(x^n for n in range(10)); f
f.truncate(6)

valuation()[source]¶

Return the valuation of self, that is, the power of the lowest nonzero monomial of self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(10)), implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> x.valuation()
1
>>> f = x-Integer(3); f.valuation()
0
>>> f = x**Integer(99); f.valuation()
99
>>> f = x-x; f.valuation()
+Infinity

Sage Live

R.<x> = PolynomialRing(Integers(10), implementation='NTL')
x.valuation()
f = x-3; f.valuation()
f = x^99; f.valuation()
f = x-x; f.valuation()

sage.rings.polynomial.polynomial_modn_dense_ntl.make_element(parent, args)[source]¶

sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots(self, X=None, beta=1.0, epsilon=None, **kwds)[source]¶

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

sage: N = 10001
sage: K = Zmod(10001)
sage: P.<x> = PolynomialRing(K, implementation='NTL')
sage: f = x^3 + 10*x^2 + 5000*x - 222

Python

>>> from sage.all import *
>>> N = Integer(10001)
>>> K = Zmod(Integer(10001))
>>> P = PolynomialRing(K, implementation='NTL', names=('x',)); (x,) = P._first_ngens(1)
>>> f = x**Integer(3) + Integer(10)*x**Integer(2) + Integer(5000)*x - Integer(222)

Sage Live

N = 10001
K = Zmod(10001)
P.<x> = PolynomialRing(K, implementation='NTL')
f = x^3 + 10*x^2 + 5000*x - 222

This polynomial has no roots without modular reduction (i.e. over $Z$ ):

Sage

sage: f.change_ring(ZZ).roots()
[]

Python

>>> from sage.all import *
>>> f.change_ring(ZZ).roots()
[]

Sage Live

f.change_ring(ZZ).roots()

To compute its roots we need to factor the modulus $N$ and use the Chinese remainder theorem:

Sage

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

Python

>>> from sage.all import *
>>> p, q = N.prime_divisors()
>>> f.change_ring(GF(p)).roots()
[(4, 1)]
>>> f.change_ring(GF(q)).roots()
[(4, 1)]

>>> crt(Integer(4), Integer(4), p, q)
4

Sage Live

p, q = N.prime_divisors()
f.change_ring(GF(p)).roots()
f.change_ring(GF(q)).roots()
crt(4, 4, p, q)

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

sage: f.small_roots()
[4]

Python

>>> from sage.all import *
>>> f.small_roots()
[4]

Sage Live

f.small_roots()

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

sage: Nbits, Kbits = 512, 56
sage: e = 3

Python

>>> from sage.all import *
>>> Nbits, Kbits = Integer(512), Integer(56)
>>> e = Integer(3)

Sage Live

Nbits, Kbits = 512, 56
e = 3

We choose two primes of size 256-bit each:

Sage

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 )

Python

>>> from sage.all import *
>>> p = Integer(2)**Integer(256) + Integer(2)**Integer(8) + Integer(2)**Integer(5) + Integer(2)**Integer(3) + Integer(1)
>>> q = Integer(2)**Integer(256) + Integer(2)**Integer(8) + Integer(2)**Integer(5) + Integer(2)**Integer(3) + Integer(2)**Integer(2) + Integer(1)
>>> N = p*q
>>> ZmodN = Zmod( N )

Sage Live

p = 2^256 + 2^8 + 2^5 + 2^3 + 1
q = 2^256 + 2^8 + 2^5 + 2^3 + 2^2 + 1
N = p*q
ZmodN = Zmod( N )

We choose a random key:

Sage

sage: K = ZZ.random_element(0, 2^Kbits)

Python

>>> from sage.all import *
>>> K = ZZ.random_element(Integer(0), Integer(2)**Kbits)

Sage Live

K = ZZ.random_element(0, 2^Kbits)

and pad it with $512 - 56 = 456$ 1s:

Sage

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)

Python

>>> from sage.all import *
>>> Kdigits = K.digits(Integer(2))
>>> M = [Integer(0)]*Kbits + [Integer(1)]*(Nbits-Kbits)
>>> for i in range(len(Kdigits)): M[i] = Kdigits[i]

>>> M = ZZ(M, Integer(2))

Sage Live

Kdigits = K.digits(2)
M = [0]*Kbits + [1]*(Nbits-Kbits)
for i in range(len(Kdigits)): M[i] = Kdigits[i]
M = ZZ(M, 2)

Now we encrypt the resulting message:

Sage

sage: C = ZmodN(M)^e

Python

>>> from sage.all import *
>>> C = ZmodN(M)**e

Sage Live

C = ZmodN(M)^e

To recover $K$ we consider the following polynomial modulo $N$ :

Sage

sage: P.<x> = PolynomialRing(ZmodN, implementation='NTL')
sage: f = (2^Nbits - 2^Kbits + x)^e - C

Python

>>> from sage.all import *
>>> P = PolynomialRing(ZmodN, implementation='NTL', names=('x',)); (x,) = P._first_ngens(1)
>>> f = (Integer(2)**Nbits - Integer(2)**Kbits + x)**e - C

Sage Live

P.<x> = PolynomialRing(ZmodN, implementation='NTL')
f = (2^Nbits - 2^Kbits + x)^e - C

and recover its small roots:

Sage

sage: Kbar = f.small_roots()[0]
sage: K == Kbar
True

Python

>>> from sage.all import *
>>> Kbar = f.small_roots()[Integer(0)]
>>> K == Kbar
True

Sage Live

Kbar = f.small_roots()[0]
K == Kbar

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

sage: length = 512
sage: hidden = 110
sage: p = next_prime(2^int(round(length/2)))
sage: q = next_prime(round(pi.n()*p))                                           # needs sage.symbolic
sage: N = p*q                                                                   # needs sage.symbolic

Python

>>> from sage.all import *
>>> length = Integer(512)
>>> hidden = Integer(110)
>>> p = next_prime(Integer(2)**int(round(length/Integer(2))))
>>> q = next_prime(round(pi.n()*p))                                           # needs sage.symbolic
>>> N = p*q                                                                   # needs sage.symbolic

Sage Live

length = 512
hidden = 110
p = next_prime(2^int(round(length/2)))
q = next_prime(round(pi.n()*p))                                           # needs sage.symbolic
N = p*q                                                                   # needs sage.symbolic

Now we disturb the low 110 bits of $q$ :

Sage

sage: qbar = q + ZZ.random_element(0, 2^hidden - 1)                             # needs sage.symbolic

Python

>>> from sage.all import *
>>> qbar = q + ZZ.random_element(Integer(0), Integer(2)**hidden - Integer(1))                             # needs sage.symbolic

Sage Live

qbar = q + ZZ.random_element(0, 2^hidden - 1)                             # needs sage.symbolic

And try to recover $q$ from it:

Sage

sage: F.<x> = PolynomialRing(Zmod(N), implementation='NTL')                     # needs sage.symbolic
sage: f = x - qbar                                                              # needs sage.symbolic

Python

>>> from sage.all import *
>>> F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',)); (x,) = F._first_ngens(1)# needs sage.symbolic
>>> f = x - qbar                                                              # needs sage.symbolic

Sage Live

F.<x> = PolynomialRing(Zmod(N), implementation='NTL')                     # needs sage.symbolic
f = x - qbar                                                              # needs sage.symbolic

We know that the error is $\leq 2^{hidden} - 1$ and that the modulus we are looking for is $\geq \sqrt{N}$ :

Sage

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               # needs sage.symbolic
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                                                             # needs sage.symbolic
True

Python

>>> from sage.all import *
>>> from sage.misc.verbose import set_verbose
>>> set_verbose(Integer(2))
>>> d = f.small_roots(X=Integer(2)**hidden-Integer(1), beta=RealNumber('0.5'))[Integer(0)]  # time random               # needs sage.symbolic
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)
>>> q == qbar - d                                                             # needs sage.symbolic
True

Sage Live

from sage.misc.verbose import set_verbose
set_verbose(2)
d = f.small_roots(X=2^hidden-1, beta=0.5)[0]  # time random               # needs sage.symbolic
q == qbar - d                                                             # needs sage.symbolic

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¶