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[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

compose_mod(other, modulus)[source]¶

Compute \(f(g) \pmod 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)) \bmod 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

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

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]

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

modular_composition(other, modulus)[source]¶

Compute \(f(g) \pmod 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)) \bmod 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

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

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

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]

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

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

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

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)

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

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

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

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

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

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

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

Bases: Polynomial_dense_mod_n

Polynomial on \(\ZZ/n\ZZ\) 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

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

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

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

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

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

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

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.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^\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

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)

This polynomial has no roots without modular reduction (i.e. over \(\ZZ\)):

Sage

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

Python

>>> from sage.all import *
>>> 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

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]

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)

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 )

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)

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))

Now we encrypt the resulting message:

Sage

sage: C = ZmodN(M)^e

Python

>>> from sage.all import *
>>> 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

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

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

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

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

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

We know that the error is \(\le 2^{\text{hidden}}-1\) and that the modulus we are looking for is \(\ge \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

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