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 be
int-sized, so we use it as default when
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:
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))
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> = Integers(100)[]
sage: p = 3*x
sage: q = 7*x
sage: p+q
10*x
sage: R.<x> = Integers(8)[]
sage: parent(p)
Univariate Polynomial Ring in x over Ring of integers modulo 100
sage: p + q
10*x
sage: R({10:-1})
7*x^10
x.__getslice__(i, j) <==> x[i:j]
Use of negative indices is not supported.
EXAMPLES:
sage: x = PolynomialRing(Integers(100), 'x').0
sage: (x - 2)*(x^2 - 8*x + 16)
x^3 + 90*x^2 + 32*x + 68
EXAMPLES:
sage: t = PolynomialRing(IntegerModRing(17),"t").gen()
sage: f = t^3 + 3*t - 17
sage: pari(f)
Mod(1, 17)*t^3 + Mod(3, 17)*t
Return a new copy of the list of the underlying elements of self.
EXAMPLES:
sage: _.<x> = Integers(100)[]
sage: f = x^3 + 3*x - 17
sage: f.list()
[83, 3, 0, 1]
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!
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))
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
Returns this polynomial multiplied by the power . If
is negative,
terms below
will be discarded. Does not change this polynomial.
EXAMPLES:
sage: R.<x> = PolynomialRing(Integers(12345678901234567890))
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:
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)
sage: f = x^3 + 10*x^2 + 5000*x - 222
sage: f.small_roots()
[4]
A dense polynomial over the integers modulo p, where p is prime.
EXAMPLES:
sage: _.<x> = PolynomialRing(GF(19))
sage: f = x^3 + 3*x - 17
sage: f.discriminant()
12
Returns the resultant of self and other, which must lie in the same polynomial ring.
INPUT:
OUTPUT: an element of the base ring of the polynomial ring
EXAMPLES:
sage: R.<x> = GF(19)['x']
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
Return the extended gcd of self and other, i.e., elements such that
Evaluate self at x. If x is a single argument coercible into the base ring of self, this is done directly in NTL, otherwise the generic Polynomial call code is used.
EXAMPLES:
sage: R.<x> = Integers(10^30)[]
sage: f = x^3+7
sage: f(5)
132
sage: f(5r)
132
sage: f(mod(5, 10^50))
132
sage: f(x)
x^3 + 7
sage: S.<y> = Integers(5)[]
sage: f(y)
y^3 + 2
Returns the whole part of self/right, without remainder.
For q = n // d, we have deg(n - q*d) < deg(d)
EXAMPLES:
sage: R.<x> = Integers(10^30)[]
sage: f = x^7 + 1; g = x^2 - 1
sage: q = f // g; q
x^5 + x^3 + x
sage: f - q*g
x + 1
EXAMPLES:
sage: R.<x> = Integers(10^30)[]
sage: f = (x+2)^7
sage: f[3]
560
x.__getslice__(i, j) <==> x[i:j]
Use of negative indices is not supported.
TEST:
sage: R.<x> = Integers(14^30)[]
sage: f = x^5 + 2*x + 1
sage: f << 3
x^8 + 2*x^4 + x^3
EXAMPLES:
sage: R.<x> = Integers(9^30)[]
sage: f = x^7 + x + 1; g = x^3 - 1
sage: r = f % g; r
2*x + 1
sage: g * (x^4 + x) + r
x^7 + x + 1
TEST:
sage: R.<x> = Integers(15^30)[]
sage: f = x^5 + 2*x + 1
sage: f >> 3
x^2
TESTS:
sage: R.<x> = Integers(10^30)[]
sage: (x+5) + (x^2 - 6)
x^2 + x + 999999999999999999999999999999
Returns the formal derivative of self with respect to var.
var must be either the generator of the polynomial ring to which this polynomial belongs, or None (either way the behaviour is the same).
See also
derivative()
EXAMPLES:
sage: R.<x> = Integers(12^29)[]
sage: f = x^4 + x + 5
sage: f._derivative()
4*x^3 + 1
sage: f._derivative(None)
4*x^3 + 1
sage: f._derivative(2*x)
...
ValueError: cannot differentiate with respect to 2*x
sage: y = var("y")
sage: f._derivative(y)
...
ValueError: cannot differentiate with respect to y
TESTS:
sage: R.<x> = Integers(10^30)[]
sage: 3 * (x+5)
3*x + 15
TESTS:
sage: R.<x> = Integers(10^30)[]
sage: (x+5) * (x^2 - 1)
x^3 + 5*x^2 + 999999999999999999999999999999*x + 999999999999999999999999999995
TESTS:
sage: R.<x> = Integers(10^30)[]
sage: (x+5) * 3
3*x + 15
TESTS:
sage: R.<x> = Integers(10^30)[]
sage: (x+5) - (x^2 - 6)
999999999999999999999999999999*x^2 + x + 11
EXAMPLES:
sage: R.<x> = Integers(14^34)[]
sage: f = x^4 - x - 1
sage: f.degree()
4
sage: f = 14^43*x + 1
sage: f.degree()
0
Returns and
, with the degree of
less than the degree of
,
such that
.
EXAMPLES:
sage: R.<x> = Integers(10^30)[]
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
Reverses the coefficients of self. The reverse of is
.
The degree will go down if the constant term is zero.
EXAMPLES:
sage: R.<x> = Integers(12^29)[]
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 self to left by , which is multiplication by
,
truncating if
is negative.
EXAMPLES:
sage: R.<x> = Integers(12^30)[]
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
Returns this polynomial mod .
EXAMPLES:
sage: R.<x> = Integers(15^30)[]
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
Returns the valuation of self, that is, the power of the lowest non-zero monomial of self.
EXAMPLES:
sage: R.<x> = Integers(10^50)[]
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
Evaluate self at x. If x is a single argument coercible into the base ring of self, this is done directly in NTL, otherwise the generic Polynomial call code is used.
EXAMPLES:
sage: R.<x> = Integers(100)[]
sage: f = x^3+7
sage: f(5)
32
sage: f(5r)
32
sage: f(mod(5, 1000))
32
sage: f(x)
x^3 + 7
sage: S.<y> = Integers(5)[]
sage: f(y)
y^3 + 2
Returns the whole part of self/right, without remainder.
For q = n // d, we have deg(n - q*d) < deg(d)
EXAMPLES:
sage: R.<x> = Integers(25)[]
sage: f = x^7 + 1; g = x^2 - 1
sage: q = f // g; q
x^5 + x^3 + x
sage: f - q*g
x + 1
EXAMPLES:
sage: R.<x> = Integers(100)[]
sage: f = (x+2)^7
sage: f[3]
60
x.__getslice__(i, j) <==> x[i:j]
Use of negative indices is not supported.
TEST:
sage: R.<x> = Integers(77)[]
sage: f = x^5 + 2*x + 1
sage: f << 3
x^8 + 2*x^4 + x^3
EXAMPLES:
sage: R.<x> = Integers(81)[]
sage: f = x^7 + x + 1; g = x^3
sage: r = f % g; r
x + 1
sage: g * x^4 + r
x^7 + x + 1
TEST:
sage: R.<x> = Integers(77)[]
sage: f = x^5 + 2*x + 1
sage: f >> 3
x^2
TESTS:
sage: R.<x> = Integers(100)[]
sage: (x+5) + (x^2 - 6)
x^2 + x + 99
Returns the formal derivative of self with respect to var.
var must be either the generator of the polynomial ring to which this polynomial belongs, or None (either way the behaviour is the same).
See also
derivative()
EXAMPLES:
sage: R.<x> = Integers(77)[]
sage: f = x^4 - x - 1
sage: f._derivative()
4*x^3 + 76
sage: f._derivative(None)
4*x^3 + 76
sage: f._derivative(2*x)
...
ValueError: cannot differentiate with respect to 2*x
sage: y = var("y")
sage: f._derivative(y)
...
ValueError: cannot differentiate with respect to y
TESTS:
sage: R.<x> = Integers(100)[]
sage: 3 * (x+5)
3*x + 15
TESTS:
sage: R.<x> = Integers(100)[]
sage: (x+5) * (x^2 - 1)
x^3 + 5*x^2 + 99*x + 95
TESTS:
sage: R.<x> = Integers(100)[]
sage: (x+5) * 3
3*x + 15
TESTS:
sage: R.<x> = Integers(100)[]
sage: (x+5) - (x^2 - 6)
99*x^2 + x + 11
EXAMPLES:
sage: R.<x> = Integers(77)[]
sage: f = x^4 - x - 1
sage: f.degree()
4
sage: f = 77*x + 1
sage: f.degree()
0
Returns the coefficients of self as efficiently as possible as a list of python ints.
EXAMPLES:
sage: R.<x> = Integers(100)[]
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'>]
Returns and
, with the degree of
less than the degree of
,
such that
.
EXAMPLES:
sage: R.<x> = Integers(125)[]
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
Reverses the coefficients of self. The reverse of is
.
The degree will go down if the constant term is zero.
EXAMPLES:
sage: R.<x> = Integers(77)[]
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 self to left by , which is multiplication by
,
truncating if
is negative.
EXAMPLES:
sage: R.<x> = Integers(77)[]
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
Returns this polynomial mod .
EXAMPLES:
sage: R.<x> = Integers(77)[]
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
Returns the valuation of self, that is, the power of the lowest non-zero monomial of self.
EXAMPLES:
sage: R.<x> = Integers(10)[]
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
Let 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
of
with the constraint that
.
Small in this context means that if
is a root of
modulo
then
. This
is either provided by the
user or the maximum
is chosen such that this algorithm
terminates in polynomial time. If
is chosen automatically
it is
.
The algorithm may also return some roots which are larger than
.
‘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:
EXAMPLES:
First consider a small example:
sage: N = 10001
sage: K = Zmod(10001)
sage: P.<x> = PolynomialRing(K)
sage: f = x^3 + 10*x^2 + 5000*x - 222
This polynomial has no roots without modular reduction (i.e. over ):
sage: f.change_ring(ZZ).roots()
[]
To compute its roots we need to factor the modulus 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 , so we can attempt to
recover it without factoring
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 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
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 we consider the following polynomial modulo
:
sage: P.<x> = PolynomialRing(ZmodN)
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 if partial
knowledge about
is available. This example is from the
Magma handbook:
First, we set up ,
and
:
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 :
sage: qbar = q + ZZ.random_element(0,2^hidden-1)
And try to recover from it:
sage: F.<x> = PolynomialRing(Zmod(N))
sage: f = x - qbar
We know that the error is and that the modulus
we are looking for is
:
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.informatik.tu-darmstadt.de/KP/publications/03/bp.ps