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
) |
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]
) |
) |
Returns deg(modulus) for GF2E elements
) |
Yields copy of the current GF2E modulus
) |
Returns a random element from GF2E modulo the current modulus.
) |
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
) |
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]
) |
) |
) |
) |
) |
Return a random number modulo p.
) |
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)
) |
Return a pseudo-random number between 0 and
sage: [ntl.ZZ_random_bits(20) for i in range(3)] [1025619, 177635, 766262]
Author: Didier Deshommes (dfdeshom@gmail.com)
) |
Returns whether hex representation is chosen or not.
OUTPUT: True if hex representation is set
) |
Seed the NTL random number generator.
sage: ntl.ntl_setSeed(10) sage: ntl.ZZ_random(1000) 776
) |
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'
) |
Represent GF2X and GF2E elements in the more compact hexadecimal form to the user.
INPUT: have_hex if True hex representation will be used
) |
Class: GF2E_class
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
) |
Returns a copy of this element.
) |
Returns True if this element equals one, False otherwise.
) |
Returns True if this element equals zero, False otherwise.
) |
Returns a ntl.GF2X copy of this element.
) |
Returns the trace of this element.
Special Functions: __add__,
__cmp__,
__mul__,
__neg__,
__pow__,
__radd__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__,
_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
Special Functions: __add__,
__mul__,
__neg__,
__pow__,
__radd__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__
Class: GF2X_class
Functions: bin,
degree,
hex,
list
) |
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
) |
Returns the degree of this polynomial
) |
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
) |
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_
) |
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
Functions: determinant,
echelon_form,
is_zero,
list,
ncols,
nrows,
transpose
) |
Returns the determinant.
) |
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?
) |
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]]
) |
Number of columns
) |
Number of rows
) |
Returns the transposed matrix of self.
OUTPUT: transposed Matrix
Special Functions: __add__,
__delitem__,
__getitem__,
__mul__,
__pow__,
__radd__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__,
_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
Functions: determinant,
echelon_form,
is_zero,
list,
ncols,
nrows,
transpose
) |
Returns the determinant.
) |
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?
) |
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]]
) |
Number of columns
) |
Number of rows
) |
Returns the transposed matrix of self.
OUTPUT: transposed Matrix
Special Functions: __add__,
__delitem__,
__getitem__,
__mul__,
__pow__,
__radd__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__,
_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
Functions: charpoly,
determinant,
HNF,
ncols,
nrows
) |
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
Functions: charpoly,
determinant,
HNF,
ncols,
nrows
) |
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
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
Objects of the class ZZ_p are represented as a ZZ
in the
range
.
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
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
) |
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]
) |
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 []
) |
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
) |
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
) |
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]
) |
Return the discriminant of a=self, which is by definition
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
) |
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]
) |
Compute and return the inverse of self modulo
.
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]
) |
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]
) |
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
) |
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
) |
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
) |
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
) |
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]
) |
Assumes that input is monic, and has deg(f) distinct roots. Returns the list of roots.
) |
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
moduluo
, its minimal polynomial
is of degree
.
sage: f.minpoly_mod(g) [0 0 1]
) |
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]
) |
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]
) |
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]
) |
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]
) |
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
) |
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
) |
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) []
) |
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 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
) |
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]
) |
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]
) |
Return the list of traces of the powers
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.
) |
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
) |
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) []
) |
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
Polynomial multiplication is very fast, and is implemented using one of 4 different algorithms:
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
) |
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
.
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]
) |
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 []
) |
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
) |
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
) |
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
) |
Return the derivative of this polynomial.
sage: f = ntl.ZZX([1,7,0,13]) sage: f.derivative() [7 0 39]
) |
Return the discriminant of self, which is by definition
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
sage: f = ntl.ZZX([1,2,0,3]) sage: f.discriminant() -339 sage: f.discriminant(proof=False) -339
) |
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]
) |
Compute and return the inverse of self modulo
.
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]
) |
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]
) |
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
) |
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
) |
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
) |
Return the least common multiple of self and other.
) |
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
) |
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]
) |
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
.
sage: f = ntl.ZZX([0,0,1]) sage: g = f*f sage: f.charpoly_mod(g) [0 0 0 0 1]
However, since
moduluo
, its minimal polynomial
is of degree
.
sage: f.minpoly_mod_noproof(g) [0 0 1]
) |
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]
) |
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]
) |
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
.
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]
) |
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]
) |
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() []
) |
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])
) |
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
) |
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
.
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
) |
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) []
) |
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 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
) |
Return f*f.
sage: f = ntl.ZZX([-1,0,1]) sage: f*f [1 0 -2 0 1]
) |
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]
) |
Return the list of traces of the powers
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.
) |
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
) |
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) []
) |
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
.
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.