5.2 Victor Shoup's NTL C++ Library

Module: sage.libs.ntl.all

SAGE provides an interface to Victor Shoup's C++ library NTL. Features of this library include incredibly fast arithmetic with polynomials and assymptotically fast factorization of polynomials.

Module-level Functions

GF2E( )

Constructs a new finite field element in GF(2**x).

A modulus emphmust have been set with codentl.set_GF2E_modulus(ntl.GF2X(<value>)) when calling this constructor. A value may be passed to this constructor. If you pass a string to the constructor please note that byte sequences and the hexadecimal notation are Little Endian in NTL. So e.g. '[0 1]' == '0x2' == x.

INPUT:
    x -- value to be assigned to this element. Same types as ntl.GF2X() are
accepted.

OUTPUT:
    a new ntl.GF2E element

sage: m=ntl.set_GF2E_modulus(ntl.GF2X([1,1,0,1,1,0,0,0,1]))
sage: ntl.GF2E(ntl.ZZ_pX([1,1,3]))
[1 1 1]
sage: ntl.GF2E('0x1c')
[1 0 0 0 0 0 1 1]
sage: ntl.GF2E('[1 0 1 0]')
[1 0 1]
sage: ntl.GF2E([1,0,1,0])
[1 0 1]
sage: ntl.GF2E(GF(2**8).gen()**20)
[0 0 1 0 1 1 0 1]

GF2EX( )

GF2E_degree( )

Returns deg(modulus) for GF2E elements

GF2E_modulus( )

Yields copy of the current GF2E modulus

GF2E_random( )

Returns a random element from GF2E modulo the current modulus.

GF2E_sage( )

Returns a SAGE FiniteField element matching the current modulus.

sage: ntl.set_GF2E_modulus([1,1,0,1,1,0,0,0,1])
sage: ntl.GF2E_sage()
Finite Field in a of size 2^8

GF2X( )

Constructs a new polynomial over GF(2).

A value may be passed to this constructor. If you pass a string to the constructor please note that byte sequences and the hexadecimal notation are little endian. So e.g. '[0 1]' == '0x2' == x.

Input types are ntl.ZZ_px, strings, lists of digits, FiniteFieldElements from extension fields over GF(2), Polynomials over GF(2), Integers, and finite extension fields over GF(2) (uses modulus).

INPUT:
    x -- value to be assigned to this element. See examples.

OUTPUT:
    a new ntl.GF2X element

sage: ntl.GF2X(ntl.ZZ_pX([1,1,3]))
[1 1 1]
sage: ntl.GF2X('0x1c')
[1 0 0 0 0 0 1 1]
sage: ntl.GF2X('[1 0 1 0]')
[1 0 1]
sage: ntl.GF2X([1,0,1,0])
[1 0 1]
sage: ntl.GF2X(GF(2**8).gen()**20)
[0 0 1 0 1 1 0 1]
sage: ntl.GF2X(GF(2**8))
[1 0 1 1 1 0 0 0 1]
sage: ntl.GF2X(2)
[0 1]

ZZ( )

ZZX( )

ZZ_p( )

ZZ_pX( )

ZZ_p_random( )

Return a random number modulo p.

ZZ_random( )

Returns cryptographically-secure random number in the range [0,n)

sage: [ntl.ZZ_random(99999) for i in range(5)]
[53357, 19674, 69528, 87029, 28752]

Author: Didier Deshommes (dfdeshom@gmail.com)

ZZ_random_bits( )

Return a pseudo-random number between 0 and $ 2^n-1$

sage: [ntl.ZZ_random_bits(20) for i in range(3)]
[1025619, 177635, 766262]

Author: Didier Deshommes (dfdeshom@gmail.com)

have_hex_output( )

Returns whether hex representation is chosen or not.

OUTPUT: True if hex representation is set

ntl_setSeed( )

Seed the NTL random number generator.

sage: ntl.ntl_setSeed(10)
sage: ntl.ZZ_random(1000)
776

set_GF2E_modulus( )

Initializes the current modulus to P required: deg(P) >= 1

The input is either ntl.GF2X or is tried to be converted to a ntl.GF2X element.

INPUT:
    x -- modulus

sage: ntl.set_GF2E_modulus([1,1,0,1,1,0,0,0,1])
sage: ntl.GF2E_modulus().hex()
'0xb11'

set_hex_output( )

Represent GF2X and GF2E elements in the more compact hexadecimal form to the user.

INPUT:
    have_hex if True hex representation will be used

set_modulus( )

Class: GF2E_class

class GF2E_class
The
classGF2E represents a finite extension field over GF(2) using NTL. Elements are represented as polynomials over GF(2) modulo
codentl.GF2E_modulus().

This modulus must be set using
code ntl.set_GF2E_modulus() and is unique for alle elements in ntl.GF2E. So it is not possible at the moment e.g. to have elements in GF(2**4) and GF(2**8) at the same time. You might however be lucky and get away with not touch the elements in GF(2**4) while having the GF(2**8) modulus set and vice versa.

Functions: copy,$  $ is_one,$  $ is_zero,$  $ ntl_GF2X,$  $ trace

copy( )

Returns a copy of this element.

is_one( )

Returns True if this element equals one, False otherwise.

is_zero( )

Returns True if this element equals zero, False otherwise.

ntl_GF2X( )

Returns a ntl.GF2X copy of this element.

trace( )

Returns the trace of this element.

Special Functions: __add__,$  $ __cmp__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __sub__,$  $ _sage_

_sage_( )

Returns a classFiniteFieldElement representation of this element. If a classFiniteField k is provided it is constructed in this field if possible. A classFiniteField will be constructed if none is provided.

INPUT:
    self  -- class{GF2E} element
    k     -- optional GF(2**deg)
    cache -- optional NTL to SAGE conversion dictionary

OUTPUT:
    FiniteFieldElement over k

Class: GF2EX_class

class GF2EX_class

Special Functions: __add__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __sub__

Class: GF2X_class

class GF2X_class
Polynomials over GF(2) via NTL

Functions: bin,$  $ degree,$  $ hex,$  $ list

bin( )

Returns binary representation of this element. It is the same as setting codentl.set_hex_output(False) and representing this element afterwards. However it should be faster and preserves the HexOutput state as opposed to the above code.

sage: e=ntl.GF2X([1,1,0,1,1,1,0,0,1])
sage: e.bin()
'[1 1 0 1 1 1 0 0 1]'

OUTPUT: string representing this element in binary digits

degree( )

Returns the degree of this polynomial

hex( )

Returns hexadecimal representation of this element. It is the same as setting codentl.set_hex_output(True) and representing this element afterwards. However it should be faster and preserves the HexOutput state as opposed to the above code.

sage: e=ntl.GF2X([1,1,0,1,1,1,0,0,1])
sage: e.hex()
'0xb31'

OUTPUT: string representing this element in hexadecimal

list( )

Represents this element as a list of binary digits.

sage: e=ntl.GF2X([0,1,1])
sage: e.list()
[0, 1, 1]
sage: e=ntl.GF2X('0xff')
sage: e.list()
[1, 1, 1, 1, 1, 1, 1, 1]

OUTPUT: a list of digits representing the coefficients in this element's polynomial representation

Special Functions: __add__,$  $ __cmp__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __sub__,$  $ _sage_

_sage_( )

Returns a SAGE polynomial over GF(2) equivalent to this element. If a ring R is provided it is used to construct the polynomial in, otherwise an appropriate ring is generated.

INPUT:
    self  -- GF2X element
    R     -- PolynomialRing over GF(2)
    cache -- optional NTL to SAGE cache (dict)

OUTPUT:
    polynomial in R

Class: mat_GF2E

class mat_GF2E
The mat_GF2E class implements arithmetic with matrices over $ GF(2**x)$ .

Functions: determinant,$  $ echelon_form,$  $ is_zero,$  $ list,$  $ ncols,$  $ nrows,$  $ transpose

determinant( )

Returns the determinant.

echelon_form( )

Performs unitary row operations so as to bring this matrix into row echelon form. If the optional argument codencols is supplied, stops when first ncols columns are in echelon form. The return value is the rank (or the rank of the first ncols columns).

INPUT:
   ncols -- number of columns to process

TODO: what is the output; does it return the rank?

list( )

Returns a list of the entries in this matrix

sage: ntl.set_GF2E_modulus([1,1,0,1,1,0,0,0,1])
sage: m = ntl.mat_GF2E(2,2,[ntl.GF2E_random() for x in xrange(2*2)])
sage: m.list()                   # random output
[[1 0 1 0 1 0 1 1], [0 1 0 0 0 0 1], [0 0 0 1 0 0 1], [1 1 1 0 0 0 0 1]]

ncols( )

Number of columns

nrows( )

Number of rows

transpose( )

Returns the transposed matrix of self.

OUTPUT: transposed Matrix

Special Functions: __add__,$  $ __delitem__,$  $ __getitem__,$  $ __mul__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __setitem__,$  $ __sub__,$  $ _sage_

_sage_( )

Returns a classMatrix over a FiniteField representation of this element.

INPUT:
    self  -- class{mat_GF2E} element
    k     -- optional GF(2**deg)
    cache -- optional NTL to SAGE conversion dictionary

OUTPUT:
    Matrix over k

Class: mat_GF2E_class

class mat_GF2E_class
The mat_GF2E class implements arithmetic with matrices over $ GF(2**x)$ .

Functions: determinant,$  $ echelon_form,$  $ is_zero,$  $ list,$  $ ncols,$  $ nrows,$  $ transpose

determinant( )

Returns the determinant.

echelon_form( )

Performs unitary row operations so as to bring this matrix into row echelon form. If the optional argument codencols is supplied, stops when first ncols columns are in echelon form. The return value is the rank (or the rank of the first ncols columns).

INPUT:
   ncols -- number of columns to process

TODO: what is the output; does it return the rank?

list( )

Returns a list of the entries in this matrix

sage: ntl.set_GF2E_modulus([1,1,0,1,1,0,0,0,1])
sage: m = ntl.mat_GF2E(2,2,[ntl.GF2E_random() for x in xrange(2*2)])
sage: m.list()                   # random output
[[1 0 1 0 1 0 1 1], [0 1 0 0 0 0 1], [0 0 0 1 0 0 1], [1 1 1 0 0 0 0 1]]

ncols( )

Number of columns

nrows( )

Number of rows

transpose( )

Returns the transposed matrix of self.

OUTPUT: transposed Matrix

Special Functions: __add__,$  $ __delitem__,$  $ __getitem__,$  $ __mul__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __setitem__,$  $ __sub__,$  $ _sage_

_sage_( )

Returns a classMatrix over a FiniteField representation of this element.

INPUT:
    self  -- class{mat_GF2E} element
    k     -- optional GF(2**deg)
    cache -- optional NTL to SAGE conversion dictionary

OUTPUT:
    Matrix over k

Class: mat_ZZ

class mat_ZZ
The mat_ZZ class implements arithmetic with matrices over $ \mathbf{Z}$ .

Functions: charpoly,$  $ determinant,$  $ HNF,$  $ ncols,$  $ nrows

HNF( )

The input matrix A=self is an n x m matrix of rank m (so n >= m), and D is a multiple of the determinant of the lattice L spanned by the rows of A. The output W is the Hermite Normal Form of A; that is, W is the unique m x m matrix whose rows span L, such that

- W is lower triangular, - the diagonal entries are positive, - any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.

This is implemented using the algorithm of [P. Domich, R. Kannan and L. Trotter, Math. Oper. Research 12:50-59, 1987].

TIMINGS: NTL isn't very good compared to MAGMA, unfortunately:

sage: import ntl
sage: a=MatrixSpace(Q,200).random_element()    # -2 to 2
sage: A=ntl.mat_ZZ(200,200)
sage: for i in xrange(a.nrows()):
   ....:     for j in xrange(a.ncols()):
   ....:         A[i,j] = a[i,j]
   ....:
sage: time d=A.determinant()
Time.: 3.89 seconds
sage: time B=A.HNF(d)
Time.: 27.59 seconds

In comparison, MAGMA does this much more quickly:

            > A := MatrixAlgebra(Z,200)![Random(-2,2) : i in [1..200^2]];
            > time d := Determinant(A);
            Time: 0.710
            > time H := HermiteForm(A);
            Time: 3.080

Also, PARI is also faster than NTL if one uses the flag 1 to the mathnf routine. The above takes 16 seconds in PARI.

Special Functions: __add__,$  $ __delitem__,$  $ __getitem__,$  $ __mul__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __setitem__,$  $ __sub__

Class: mat_ZZ_class

class mat_ZZ_class
The mat_ZZ class implements arithmetic with matrices over $ \mathbf{Z}$ .

Functions: charpoly,$  $ determinant,$  $ HNF,$  $ ncols,$  $ nrows

HNF( )

The input matrix A=self is an n x m matrix of rank m (so n >= m), and D is a multiple of the determinant of the lattice L spanned by the rows of A. The output W is the Hermite Normal Form of A; that is, W is the unique m x m matrix whose rows span L, such that

- W is lower triangular, - the diagonal entries are positive, - any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.

This is implemented using the algorithm of [P. Domich, R. Kannan and L. Trotter, Math. Oper. Research 12:50-59, 1987].

TIMINGS: NTL isn't very good compared to MAGMA, unfortunately:

sage: import ntl
sage: a=MatrixSpace(Q,200).random_element()    # -2 to 2
sage: A=ntl.mat_ZZ(200,200)
sage: for i in xrange(a.nrows()):
   ....:     for j in xrange(a.ncols()):
   ....:         A[i,j] = a[i,j]
   ....:
sage: time d=A.determinant()
Time.: 3.89 seconds
sage: time B=A.HNF(d)
Time.: 27.59 seconds

In comparison, MAGMA does this much more quickly:

            > A := MatrixAlgebra(Z,200)![Random(-2,2) : i in [1..200^2]];
            > time d := Determinant(A);
            Time: 0.710
            > time H := HermiteForm(A);
            Time: 3.080

Also, PARI is also faster than NTL if one uses the flag 1 to the mathnf routine. The above takes 16 seconds in PARI.

Special Functions: __add__,$  $ __delitem__,$  $ __getitem__,$  $ __mul__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __setitem__,$  $ __sub__

Class: ZZ_class

class ZZ_class
The ZZ class is used to represent signed, arbitrary length integers.

Routines are provided for all of the basic arithmetic operations, as well as for some more advanced operations such as primality testing. Space is automatically managed by the constructors and destructors.

This module also provides routines for generating small primes, and fast routines for performing modular arithmetic on single-precision numbers.

Special Functions: __add__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __sub__

Class: ZZ_p_class

class ZZ_p_class
The ZZ_p class is used to represent integers modulo $ p$ . The modulus $ p$ may be any positive integer, not necessarily prime.

Objects of the class ZZ_p are represented as a ZZ in the range $ 0, \ldots, p-1$ .

An executing program maintains a "current modulus", which is set to p with ntl_ZZ_p.init(p). The current modulus should be initialized before any ZZ_p objects are created.

The modulus may be changed, and a mechanism is provided for saving and restoring a modulus (see classes ZZ_pBak and ZZ_pContext below).

TODO: This documentation is wrong

Special Functions: __add__,$  $ __cmp__,$  $ __invert__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __repr__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __sub__

Class: ZZ_pX_class

class ZZ_pX_class
The class ZZ_pX implements polynomial arithmetic modulo $ p$ .

Polynomial arithmetic is implemented using the FFT, combined with the Chinese Remainder Theorem. A more detailed description of the techniques used here can be found in [Shoup, J. Symbolic Comp. 20:363-397, 1995].

Small degree polynomials are multiplied either with classical or Karatsuba algorithms.

Functions: charpoly_mod,$  $ clear,$  $ constant_term,$  $ copy,$  $ degree,$  $ derivative,$  $ discriminant,$  $ factor,$  $ gcd,$  $ invert_and_truncate,$  $ is_monic,$  $ is_one,$  $ is_x,$  $ is_zero,$  $ leading_coefficient,$  $ left_shift,$  $ linear_roots,$  $ minpoly_mod,$  $ multiply_and_truncate,$  $ multiply_mod,$  $ norm_mod,$  $ preallocate_space,$  $ quo_rem,$  $ resultant,$  $ reverse,$  $ right_shift,$  $ set_x,$  $ square,$  $ square_and_truncate,$  $ trace_list,$  $ trace_mod,$  $ truncate,$  $ xgcd

charpoly_mod( )

Return the characteristic polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self.

sage: ntl.set_modulus(ntl.ZZ(17))                
sage: f = ntl.ZZ_pX([1,2,0,3])
sage: mod = ntl.ZZ_pX([-5,2,0,0,1])
sage: f.charpoly_mod(mod)
[11 1 8 14 1]

clear( )

Reset this polynomial to 0. Changes this polynomial in place.

sage: ntl.set_modulus(ntl.ZZ(17))        
sage: f = ntl.ZZ_pX([1,2,3])
sage: f
[1 2 3]
sage: f.clear()
sage: f
[]

constant_term( )

Return the constant coefficient of this polynomial.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([3,6,9])
sage: f.constant_term()
3
sage: f = ntl.ZZ_pX()
sage: f.constant_term()
0

degree( )

Return the degree of this polynomial. The degree of the 0 polynomial is -1.

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([5,0,1])
sage: f.degree()
2
sage: f = ntl.ZZ_pX(range(100))
sage: f.degree()
99
sage: f = ntl.ZZ_pX()
sage: f.degree()
-1
sage: f = ntl.ZZ_pX([1])
sage: f.degree()
0

derivative( )

Return the derivative of this polynomial.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([1,7,0,13])
sage: f.derivative()
[7 0 19]

discriminant( )

Return the discriminant of a=self, which is by definition

$\displaystyle (-1)^{m(m-1)/2} {\mbox{\tt resultant}}(a, a')/lc(a),
$

where m = deg(a), and lc(a) is the leading coefficient of a.

sage: ntl.set_modulus(ntl.ZZ(17))                
sage: f = ntl.ZZ_pX([1,2,0,3])
sage: f.discriminant()
1

gcd( )

Return the gcd d = gcd(a, b), where by convention the leading coefficient of d is >= 0. We uses a multi-modular algorithm.

sage: ntl.set_modulus(ntl.ZZ(17))        
sage: f = ntl.ZZ_pX([1,2,3]) * ntl.ZZ_pX([4,5])**2
sage: g = ntl.ZZ_pX([1,1,1])**3 * ntl.ZZ_pX([1,2,3])
sage: f.gcd(g)
[6 12 1]
sage: g.gcd(f)
[6 12 1]

invert_and_truncate( )

Compute and return the inverse of self modulo $ x^m$ . The constant term of self must be 1 or -1.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([1,2,3,4,5,6,7])
sage: f.invert_and_truncate(20)
[1 18 1 0 0 0 0 8 17 2 13 0 0 0 4 0 17 10 9]
sage: g = f.invert_and_truncate(20)
sage: g * f
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 4 4 3]

is_monic( )

Return True exactly if this polynomial is monic.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([2,0,0,1])
sage: f.is_monic()
True
sage: g = f.reverse()
sage: g.is_monic()
False
sage: g
[1 0 0 2]

is_one( )

Return True exactly if this polynomial is 1.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([1,1])
sage: f.is_one()
False
sage: f = ntl.ZZ_pX([1])
sage: f.is_one()
True

is_x( )

True if this is the polynomial "x".

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX()
sage: f.set_x()
sage: f.is_x()
True
sage: f = ntl.ZZ_pX([0,1])
sage: f.is_x()
True
sage: f = ntl.ZZ_pX([1])
sage: f.is_x()
False

is_zero( )

Return True exactly if this polynomial is 0.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([0,0,0,20])
sage: f.is_zero()
True
sage: f = ntl.ZZ_pX([0,0,1])
sage: f
[0 0 1]
sage: f.is_zero()
False

leading_coefficient( )

Return the leading coefficient of this polynomial.

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([3,6,9])
sage: f.leading_coefficient()
9
sage: f = ntl.ZZ_pX()
sage: f.leading_coefficient()
0

left_shift( )

Return the polynomial obtained by shifting all coefficients of this polynomial to the left n positions.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([2,0,0,1])
sage: f
[2 0 0 1]
sage: f.left_shift(2)
[0 0 2 0 0 1]
sage: f.left_shift(5)
[0 0 0 0 0 2 0 0 1]

A negative left shift is a right shift.

sage: f.left_shift(-2)
[0 1]

linear_roots( )

Assumes that input is monic, and has deg(f) distinct roots. Returns the list of roots.

minpoly_mod( )

Return the minimal polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self.

sage: ntl.set_modulus(ntl.ZZ(17))
sage: f = ntl.ZZ_pX([0,0,1])
sage: g = f*f
sage: f.charpoly_mod(g)
[0 0 0 0 1]

However, since $ f^2 = 0$ moduluo $ g$ , its minimal polynomial is of degree $ 2$ .

sage: f.minpoly_mod(g)
[0 0 1]

multiply_and_truncate( )

Return self*other but with terms of degree >= m removed.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([1,2,3,4,5])
sage: g = ntl.ZZ_pX([10])
sage: f.multiply_and_truncate(g, 2)
[10]
sage: g.multiply_and_truncate(f, 2)
[10]

multiply_mod( )

Return self*other deg(modulus) > 0, and self and other must have smaller degree.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: modulus = ntl.ZZ_pX([1,2,0,1])    # must be monic
sage: g = ntl.ZZ_pX([-1,0,1])
sage: h = ntl.ZZ_pX([3,7,13])
sage: h.multiply_mod(g, modulus)
[10 6 4]

norm_mod( )

Return the norm of this polynomial modulo the modulus. The modulus must be monic, and of positive degree strictly greater than the degree of self.

sage: ntl.set_modulus(ntl.ZZ(17))                
sage: f = ntl.ZZ_pX([1,2,0,3])
sage: mod = ntl.ZZ_pX([-5,2,0,0,1])
sage: f.norm_mod(mod)
11

The norm is the constant term of the characteristic polynomial.

sage: f.charpoly_mod(mod)
[11 1 8 14 1]

preallocate_space( )

Pre-allocate spaces for n coefficients. The polynomial that f represents is unchanged. This is useful if you know you'll be setting coefficients up to n, so memory isn't re-allocated as the polynomial grows. (You might save a millisecond with this function.)

sage: ntl.set_modulus(ntl.ZZ(17))        
sage: f = ntl.ZZ_pX([1,2,3])
sage: f.preallocate_space(20)
sage: f
[1 2 3]
sage: f[10]=5  # no new memory is allocated
sage: f
[1 2 3 0 0 0 0 0 0 0 5]

quo_rem( )

Returns the unique integral q and r such that self = q*other + r, if they exist. Otherwise raises an Exception.

sage: ntl.set_modulus(ntl.ZZ(17))         
sage: f = ntl.ZZ_pX(range(10)); g = ntl.ZZ_pX([-1,0,1])
sage: q, r = f.quo_rem(g)
sage: q, r
([3 7 1 4 14 16 8 9], [3 8])
sage: q*g + r == f
True

resultant( )

Return the resultant of self and other.

sage: ntl.set_modulus(ntl.ZZ(17))                
sage: f = ntl.ZZ_pX([17,0,1,1])
sage: g = ntl.ZZ_pX([34,-17,18,2])
sage: f.resultant(g)
0

reverse( )

Return the polynomial obtained by reversing the coefficients of this polynomial. If hi is set then this function behaves as if this polynomial has degree hi.

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([1,2,3,4,5])
sage: f.reverse()
[5 4 3 2 1]
sage: f.reverse(hi=10)
[0 0 0 0 0 0 5 4 3 2 1]
sage: f.reverse(hi=2)
[3 2 1]
sage: f.reverse(hi=-2)
[]

right_shift( )

Return the polynomial obtained by shifting all coefficients of this polynomial to the right n positions.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([2,0,0,1])
sage: f
[2 0 0 1]
sage: f.right_shift(2)
[0 1]
sage: f.right_shift(5)
[]
sage: f.right_shift(-2)
[0 0 2 0 0 1]

set_x( )

Set this polynomial to the monomial "x".

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX()
sage: f.set_x()
sage: f
[0 1]
sage: g = ntl.ZZ_pX([0,1])
sage: f == g
True

Though f and g are equal, they are not the same objects in memory:

sage: f is g
False

square( )

Return f*f.

sage: ntl.set_modulus(ntl.ZZ(17))
sage: f = ntl.ZZ_pX([-1,0,1])
sage: f*f
[1 0 15 0 1]

square_and_truncate( )

Return self*self but with terms of degree >= m removed.

sage: ntl.set_modulus(ntl.ZZ(20))        
sage: f = ntl.ZZ_pX([1,2,3,4,5])
sage: f.square_and_truncate(4)
[1 4 10]
sage: (f*f).truncate(4)
[1 4 10]

trace_list( )

Return the list of traces of the powers $ x^i$ of the monomial x modulo this polynomial for i = 0, ..., deg(f)-1. This polynomial must be monic.

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([1,2,0,3,0,1])
sage: f.trace_list()
[5, 0, 14, 0, 10]

The input polynomial must be monic or a ValueError is raised:

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([1,2,0,3,0,2])
sage: f.trace_list()
Traceback (most recent call last):
...
ValueError: polynomial must be monic.

trace_mod( )

Return the trace of this polynomial modulus the modulus. The modulus must be monic, and of positive degree degree bigger than the the degree of self.

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([1,2,0,3])
sage: mod = ntl.ZZ_pX([5,3,-1,1,1])
sage: f.trace_mod(mod)
3

truncate( )

Return the truncation of this polynomial obtained by removing all terms of degree >= m.

sage: ntl.set_modulus(ntl.ZZ(20))                
sage: f = ntl.ZZ_pX([1,2,3,4,5])
sage: f.truncate(3)
[1 2 3]
sage: f.truncate(8)
[1 2 3 4 5]
sage: f.truncate(1)
[1]
sage: f.truncate(0)
[]
sage: f.truncate(-1)
[]
sage: f.truncate(-5)
[]

xgcd( )

Returns r,s,t such that r = s*self + t*other.

Here r is the resultant of a and b; if r != 0, then this function computes s and t such that: a*s + b*t = r; otherwise s and t are both 0.

sage: ntl.set_modulus(ntl.ZZ(17))                
sage: f = ntl.ZZ_pX([1,2,3]) * ntl.ZZ_pX([4,5])**2
sage: g = ntl.ZZ_pX([1,1,1])**3 * ntl.ZZ_pX([1,2,3])
sage: f.xgcd(g)   # nothing since they are not coprime
([6 12 1], [15 13 6 8 7 9], [4 13])

In this example the input quadratic polynomials have a common root modulo 13.

sage: f = ntl.ZZ_pX([5,0,1])
sage: g = ntl.ZZ_pX([18,0,1])
sage: f.xgcd(g)
([1], [13], [4])

Special Functions: __add__,$  $ __cmp__,$  $ __delitem__,$  $ __div__,$  $ __getitem__,$  $ __mod__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __rdiv__,$  $ __repr__,$  $ __rmod__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __setitem__,$  $ __sub__

Class: ZZX_class

class ZZX_class
The class ZZX implements polynomials in $ \mathbf{Z}[X]$ , i.e., univariate polynomials with integer coefficients.

Polynomial multiplication is very fast, and is implemented using one of 4 different algorithms:

  1. Classical
  2. Karatsuba
  3. Schoenhage and Strassen -- performs an FFT by working modulo a "Fermat number" of appropriate size... good for polynomials with huge coefficients and moderate degree
  4. CRT/FFT -- performs an FFT by working modulo several small primes. This is good for polynomials with moderate coefficients and huge degree.

The choice of algorithm is somewhat heuristic, and may not always be perfect.

Many thanks to Juergen Gerhard <jngerhar@plato.uni-paderborn.de> for pointing out the deficiency in the NTL-1.0 ZZX arithmetic, and for contributing the Schoenhage/Strassen code.

Extensive use is made of modular algorithms to enhance performance (e.g., the GCD algorithm and many others).

Functions: charpoly_mod,$  $ clear,$  $ constant_term,$  $ content,$  $ copy,$  $ degree,$  $ derivative,$  $ discriminant,$  $ gcd,$  $ invert_and_truncate,$  $ is_monic,$  $ is_one,$  $ is_x,$  $ is_zero,$  $ lcm,$  $ leading_coefficient,$  $ left_shift,$  $ minpoly_mod_noproof,$  $ multiply_and_truncate,$  $ multiply_mod,$  $ norm_mod,$  $ preallocate_space,$  $ primitive_part,$  $ pseudo_quo_rem,$  $ quo_rem,$  $ resultant,$  $ reverse,$  $ right_shift,$  $ set_x,$  $ square,$  $ square_and_truncate,$  $ trace_list,$  $ trace_mod,$  $ truncate,$  $ xgcd

charpoly_mod( )

Return the characteristic polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self. If proof=False (the default is True), then this function may use a randomized strategy that errors with probability no more than $ 2^{-80}$ .

sage: f = ntl.ZZX([1,2,0,3])
sage: mod = ntl.ZZX([-5,2,0,0,1])
sage: f.charpoly_mod(mod)
[-8846 -594 -60 14 1]

clear( )

Reset this polynomial to 0. Changes this polynomial in place.

sage: f = ntl.ZZX([1,2,3])
sage: f
[1 2 3]
sage: f.clear()
sage: f
[]

constant_term( )

Return the constant coefficient of this polynomial.

sage: f = ntl.ZZX([3,6,9])
sage: f.constant_term()
3
sage: f = ntl.ZZX()
sage: f.constant_term()
0

content( )

Return the content of f, which has sign the same as the leading coefficient of f. Also, our convention is that the content of 0 is 0.

sage: f = ntl.ZZX([2,0,0,2])
sage: f.content()
2
sage: f = ntl.ZZX([2,0,0,-2])
sage: f.content()
-2
sage: f = ntl.ZZX([6,12,3,9])
sage: f.content()
3
sage: f = ntl.ZZX([])
sage: f.content()
0

degree( )

Return the degree of this polynomial. The degree of the 0 polynomial is -1.

sage: f = ntl.ZZX([5,0,1])
sage: f.degree()
2
sage: f = ntl.ZZX(range(100))
sage: f.degree()
99
sage: f = ntl.ZZX()
sage: f.degree()
-1
sage: f = ntl.ZZX([1])
sage: f.degree()
0

derivative( )

Return the derivative of this polynomial.

sage: f = ntl.ZZX([1,7,0,13])
sage: f.derivative()
[7 0 39]

discriminant( )

Return the discriminant of self, which is by definition

$\displaystyle (-1)^{m(m-1)/2} {\mbox{\tt resultant}}(a, a')/lc(a),
$

where m = deg(a), and lc(a) is the leading coefficient of a. If proof is False (the default is True), then this function may use a randomized strategy that errors with probability no more than $ 2^{-80}$ .

sage: f = ntl.ZZX([1,2,0,3])
sage: f.discriminant()
-339
sage: f.discriminant(proof=False)
-339

gcd( )

Return the gcd d = gcd(a, b), where by convention the leading coefficient of d is >= 0. We use a multi-modular algorithm.

sage: f = ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])**2
sage: g = ntl.ZZX([1,1,1])**3 * ntl.ZZX([1,2,3])
sage: f.gcd(g)
[1 2 3]
sage: g.gcd(f)
[1 2 3]

invert_and_truncate( )

Compute and return the inverse of self modulo $ x^m$ . The constant term of self must be 1 or -1.

sage: f = ntl.ZZX([1,2,3,4,5,6,7])
sage: f.invert_and_truncate(20)
[1 -2 1 0 0 0 0 8 -23 22 -7 0 0 0 64 -240 337 -210 49]
sage: g = f.invert_and_truncate(20)
sage: g * f
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -512 1344 -1176 343]

is_monic( )

Return True exactly if this polynomial is monic.

sage: f = ntl.ZZX([2,0,0,1])
sage: f.is_monic()
True
sage: g = f.reverse()
sage: g.is_monic()
False
sage: g
[1 0 0 2]

is_one( )

Return True exactly if this polynomial is 1.

sage: f = ntl.ZZX([1,1])
sage: f.is_one()
False
sage: f = ntl.ZZX([1])
sage: f.is_one()
True

is_x( )

True if this is the polynomial "x".

sage: f = ntl.ZZX()
sage: f.set_x()
sage: f.is_x()
True
sage: f = ntl.ZZX([0,1])
sage: f.is_x()
True
sage: f = ntl.ZZX([1])
sage: f.is_x()
False

is_zero( )

Return True exactly if this polynomial is 0.

sage: f = ntl.ZZX([0,0,0,0])
sage: f.is_zero()
True
sage: f = ntl.ZZX([0,0,1])
sage: f
[0 0 1]
sage: f.is_zero()
False

lcm( )

Return the least common multiple of self and other.

leading_coefficient( )

Return the leading coefficient of this polynomial.

sage: f = ntl.ZZX([3,6,9])
sage: f.leading_coefficient()
9
sage: f = ntl.ZZX()
sage: f.leading_coefficient()
0

left_shift( )

Return the polynomial obtained by shifting all coefficients of this polynomial to the left n positions.

sage: f = ntl.ZZX([2,0,0,1])
sage: f
[2 0 0 1]
sage: f.left_shift(2)
[0 0 2 0 0 1]
sage: f.left_shift(5)
[0 0 0 0 0 2 0 0 1]

A negative left shift is a right shift.

sage: f.left_shift(-2)
[0 1]

minpoly_mod_noproof( )

Return the minimal polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self. In all cases, this function may use a randomized strategy that errors with probability no more than $ 2^{-80}$ .

sage: f = ntl.ZZX([0,0,1])
sage: g = f*f
sage: f.charpoly_mod(g)
[0 0 0 0 1]

However, since $ f^2 = 0$ moduluo $ g$ , its minimal polynomial is of degree $ 2$ .

sage: f.minpoly_mod_noproof(g)
[0 0 1]

multiply_and_truncate( )

Return self*other but with terms of degree >= m removed.

sage: f = ntl.ZZX([1,2,3,4,5])
sage: g = ntl.ZZX([10])
sage: f.multiply_and_truncate(g, 2)
[10 20]
sage: g.multiply_and_truncate(f, 2)
[10 20]

multiply_mod( )

Return self*other deg(modulus) > 0, and self and other must have smaller degree.

sage: modulus = ntl.ZZX([1,2,0,1])    # must be monic
sage: g = ntl.ZZX([-1,0,1])
sage: h = ntl.ZZX([3,7,13])
sage: h.multiply_mod(g, modulus)
[-10 -34 -36]

norm_mod( )

Return the norm of this polynomial modulo the modulus. The modulus must be monic, and of positive degree strictly greater than the degree of self. If proof=False (the default is proof=True) then it may use a randomized strategy that errors with probability no more than $ 2^{-80}$ .

sage: f = ntl.ZZX([1,2,0,3])
sage: mod = ntl.ZZX([-5,2,0,0,1])
sage: f.norm_mod(mod)
-8846

The norm is the constant term of the characteristic polynomial.

sage: f.charpoly_mod(mod)
[-8846 -594 -60 14 1]

preallocate_space( )

Pre-allocate spaces for n coefficients. The polynomial that f represents is unchanged. This is useful if you know you'll be setting coefficients up to n, so memory isn't re-allocated as the polynomial grows. (You might save a millisecond with this function.)

sage: f = ntl.ZZX([1,2,3])
sage: f.preallocate_space(20)
sage: f
[1 2 3]
sage: f[10]=5  # no new memory is allocated
sage: f
[1 2 3 0 0 0 0 0 0 0 5]

primitive_part( )

Return the primitive part of f. Our convention is that the leading coefficient of the primitive part is nonnegegative, and the primitive part of 0 is 0.

sage: f = ntl.ZZX([6,12,3,9])
sage: f.primitive_part()
[2 4 1 3]
sage: f
[6 12 3 9]
sage: f = ntl.ZZX([6,12,3,-9])
sage: f
[6 12 3 -9]
sage: f.primitive_part()
[-2 -4 -1 3]
sage: f = ntl.ZZX()
sage: f.primitive_part()
[]

pseudo_quo_rem( )

Performs pseudo-division: computes q and r with deg(r) < deg(b), and LeadCoeff(b)(deg(a)-deg(b)+1) a = b q + r. Only the classical algorithm is used.

sage: f = ntl.ZZX([0,1])
sage: g = ntl.ZZX([1,2,3])
sage: g.pseudo_quo_rem(f)
([2 3], [1])
sage: f = ntl.ZZX([1,1])
sage: g.pseudo_quo_rem(f)
([-1 3], [2])

quo_rem( )

Returns the unique integral q and r such that self = q*other + r, if they exist. Otherwise raises an Exception.

sage: f = ntl.ZZX(range(10)); g = ntl.ZZX([-1,0,1])
sage: q, r = f.quo_rem(g)
sage: q, r
([20 24 18 21 14 16 8 9], [20 25])
sage: q*g + r == f
True

resultant( )

Return the resultant of self and other. If proof = False (the default is proof=True), then this function may use a randomized strategy that errors with probability no more than $ 2^{-80}$ .

sage: f = ntl.ZZX([17,0,1,1])
sage: g = ntl.ZZX([34,-17,18,2])
sage: f.resultant(g)
1345873
sage: f.resultant(g, proof=False)
1345873

reverse( )

Return the polynomial obtained by reversing the coefficients of this polynomial. If hi is set then this function behaves as if this polynomial has degree hi.

sage: f = ntl.ZZX([1,2,3,4,5])
sage: f.reverse()
[5 4 3 2 1]
sage: f.reverse(hi=10)
[0 0 0 0 0 0 5 4 3 2 1]
sage: f.reverse(hi=2)
[3 2 1]
sage: f.reverse(hi=-2)
[]

right_shift( )

Return the polynomial obtained by shifting all coefficients of this polynomial to the right n positions.

sage: f = ntl.ZZX([2,0,0,1])
sage: f
[2 0 0 1]
sage: f.right_shift(2)
[0 1]
sage: f.right_shift(5)
[]
sage: f.right_shift(-2)
[0 0 2 0 0 1]

set_x( )

Set this polynomial to the monomial "x".

sage: f = ntl.ZZX()
sage: f.set_x()
sage: f
[0 1]
sage: g = ntl.ZZX([0,1])
sage: f == g
True

Though f and g are equal, they are not the same objects in memory:

sage: f is g
False

square( )

Return f*f.

sage: f = ntl.ZZX([-1,0,1])
sage: f*f
[1 0 -2 0 1]

square_and_truncate( )

Return self*self but with terms of degree >= m removed.

sage: f = ntl.ZZX([1,2,3,4,5])
sage: f.square_and_truncate(4)
[1 4 10 20]
sage: (f*f).truncate(4)
[1 4 10 20]

trace_list( )

Return the list of traces of the powers $ x^i$ of the monomial x modulo this polynomial for i = 0, ..., deg(f)-1. This polynomial must be monic.

sage: f = ntl.ZZX([1,2,0,3,0,1])
sage: f.trace_list()
[5, 0, -6, 0, 10]

The input polynomial must be monic or a ValueError is raised:

sage: f = ntl.ZZX([1,2,0,3,0,2])
sage: f.trace_list()
Traceback (most recent call last):
...
ValueError: polynomial must be monic.

trace_mod( )

Return the trace of this polynomial modulus the modulus. The modulus must be monic, and of positive degree degree bigger than the the degree of self.

sage: f = ntl.ZZX([1,2,0,3])
sage: mod = ntl.ZZX([5,3,-1,1,1])
sage: f.trace_mod(mod)
-37

truncate( )

Return the truncation of this polynomial obtained by removing all terms of degree >= m.

sage: f = ntl.ZZX([1,2,3,4,5])
sage: f.truncate(3)
[1 2 3]
sage: f.truncate(8)
[1 2 3 4 5]
sage: f.truncate(1)
[1]
sage: f.truncate(0)
[]
sage: f.truncate(-1)
[]
sage: f.truncate(-5)
[]

xgcd( )

If self and other are coprime over the rationals, return r, s, t such that r = s*self + t*other. Otherwise return 0. This is emphnot the same as the sage function on polynomials over the integers, since here the return value r is always an integer.

Here r is the resultant of a and b; if r != 0, then this function computes s and t such that: a*s + b*t = r; otherwise s and t are both 0. If proof = False (*not* the default), then resultant computation may use a randomized strategy that errs with probability no more than $ 2^{-80}$ .

sage: f = ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])**2
sage: g = ntl.ZZX([1,1,1])**3 * ntl.ZZX([1,2,3])
sage: f.xgcd(g)   # nothing since they are not coprime
(0, [], [])

In this example the input quadratic polynomials have a common root modulo 13.

sage: f = ntl.ZZX([5,0,1])
sage: g = ntl.ZZX([18,0,1])
sage: f.xgcd(g)
(169, [-13], [13])

Special Functions: __add__,$  $ __cmp__,$  $ __delitem__,$  $ __div__,$  $ __getitem__,$  $ __mod__,$  $ __mul__,$  $ __neg__,$  $ __pow__,$  $ __radd__,$  $ __rdiv__,$  $ __repr__,$  $ __rmod__,$  $ __rmul__,$  $ __rpow__,$  $ __rsub__,$  $ __setitem__,$  $ __sub__

See About this document... for information on suggesting changes.