Module: sage.libs.ntl.all
Victor Shoup's NTL C++ Library
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
) |
Create a new GF2EContext.
sage: c = ntl.GF2EContext(GF(2^2,'a')) sage: n1 = ntl.GF2E([0,1],c) sage: n1 [0 1]
) |
Returns a random element from GF2E modulo the current modulus.
Input:
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2E_random(ctx) [1 0 1 0 1 0 0 1]
) |
Represent GF2X and GF2E elements in the more compact hexadecimal form to the user.
If no parameter is provided the currently set value will be returned.
Input: have_hex if True hex representation will be used
sage: m = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], m) ; x [1 0 1 0 1]
sage: ntl.GF2XHexOutput() ## indirect doctest False sage: ntl.GF2XHexOutput(True) sage: ntl.GF2XHexOutput() True
sage: x 0x51
sage: ntl.GF2XHexOutput(False) sage: x [1 0 1 0 1]
) |
Create a new ZZ_pContext.
sage: c = ntl.ZZ_pContext(178) sage: n1 = ntl.ZZ_p(212,c) sage: n1 34
) |
Creates an ntl_ZZ_pEContext.
Such an object must be created before any ZZ_pE or ZZ_pEX objects can be used.
The context handling should be taken care of by the wrapper classes.
sage: c = ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)); c NTL modulus [1 1 1] (mod 7)
) |
Return a random number modulo p.
sage: sage.libs.ntl.ntl_ZZ_p.ntl_ZZ_p_random_element(17) 8
) |
Returns random number in the range [0,n) . According to the NTL documentation, these numbers are "cryptographically strong"; of course, that depends in part on how they are seeded.
sage: [ntl.ZZ_random(99999) for i in range(5)] [82123, 14857, 53872, 13159, 83337]
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)] [564629, 843071, 972038]
Author: Didier Deshommes (dfdeshom@gmail.com)
) |
Seed the NTL random number generator.
This is automatically called when you set the main Sage random number seed, then call any NTL routine requiring random numbers; so you should never need to call this directly.
If for some reason you do need to call this directly, then you need to get a random number from NTL (so that Sage will seed NTL), then call this function and Sage will not notice.
This is automatically seeded from the main Sage random number seed.
sage: ntl.ZZ_random(1000) 341
Now you can call this function, and it will not be overridden until the next time the main Sage random number seed is changed.
sage: ntl.ntl_setSeed(10) sage: ntl.ZZ_random(1000) 776
) |
Creation function for a zz_p context.
sage: f = ntl.zz_pContext(26) sage: f = ntl.zz_pContext(10^100) Traceback (most recent call last): ... ValueError: Modulus (=10000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000) is too big
Class: GF2
Special Functions: __add__,
__div__,
__eq__,
__ge__,
__gt__,
__init__,
__int__,
__le__,
__lt__,
__mul__,
__ne__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__
) |
sage: o = ntl.GF2(1) sage: z = ntl.GF2(0) sage: o+o 0 sage: o+z 1 sage: z+o 1 sage: z+z 0
) |
sage: o = ntl.GF2(1) sage: z = ntl.GF2(0) sage: o/o 1 sage: o/z Traceback (most recent call last): ... ZeroDivisionError
) |
Return self as an int.
sage: o = ntl.GF2(1) sage: z = ntl.GF2(0) sage: int(z) 0 sage: int(o) 1
) |
sage: o = ntl.GF2(1) sage: z = ntl.GF2(0) sage: o*o 1 sage: o*z 0 sage: z*o 0 sage: z*z 0
) |
sage: o = ntl.GF2(1) sage: z = ntl.GF2(0) sage: -z 0 sage: -o 1
) |
Serializes self.
sage: a = ntl.GF2(1) sage: loads(dumps(a)) 1
) |
Return the string representation of self.
sage: str(ntl.GF2(1)) # indirect doctest '1'
) |
sage: o = ntl.GF2(1) sage: z = ntl.GF2(0) sage: o-o 0 sage: o-z 1 sage: z-o 1 sage: z-z 0
Class: GF2E
This modulus must be set by creating a GF2EContext first and pass that context to the constructor of all elements.
Functions: IsOne,
IsZero,
list,
modulus_context,
rep,
trace
) |
Returns True if this element equals one, False otherwise.
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([0,1,0,1,1,0,0,0,1], ctx) sage: x.IsOne() False sage: y.IsOne() True
) |
Returns True if this element equals zero, False otherwise.
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([1,1,0,1,1,0,0,0,1], ctx) sage: x.IsZero() False sage: y.IsZero() True
) |
Represents this element as a list of binary digits.
sage: e=ntl.GF2E([0,1,1],GF(2^4,'a')) sage: e.list() [0, 1, 1] sage: e=ntl.GF2E('0xff',GF(2^8,'a')) 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
) |
Returns the sturcture that holds the underlying NTL GF2E modulus.
sage: ctx = ntl.GF2EContext( ntl.GF2X([1,1,0,1,1,0,0,0,1]) ) sage: a = ntl.GF2E(ntl.ZZ_pX([1,1,3],2), ctx) sage: cty = a.modulus_context(); cty NTL modulus [1 1 0 1 1 0 0 0 1] sage: ctx == cty True
) |
Returns a ntl.GF2X copy of this element.
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: a = ntl.GF2E('0x1c', ctx) sage: a.rep() [1 0 0 0 0 0 1 1] sage: type(a.rep()) <type 'sage.libs.ntl.ntl_GF2X.ntl_GF2X'>
) |
Returns the trace of this element.
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([0,1,1,0,1,1], ctx) sage: x.trace() 0 sage: y.trace() 1
Special Functions: __add__,
__copy__,
__div__,
__eq__,
__ge__,
__gt__,
__init__,
__le__,
__lt__,
__mul__,
__ne__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__,
_sage_
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([1,1,0,1,1], ctx) sage: x+y ## indirect doctest [0 1 1 1]
) |
Return a copy of self.
sage: x = ntl.GF2E([0,1,1],GF(2^4,'a')) sage: y = copy(x) sage: x == y True sage: x is y False
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([1,1,0,1,1], ctx) sage: x/y ## indirect doctest [1 0 1 0 0 1 0 1]
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([1,1,0,1,1], ctx) sage: x*y ## indirect doctest [0 0 1 1 1 0 1 1]
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) sage: -x ## indirect doctest [1 0 1 0 1]
) |
sage: ctx = ntl.GF2EContext( ntl.GF2X([1,1,0,1,1,0,0,0,1]) ) sage: a = ntl.GF2E(ntl.ZZ_pX([1,1,3],2), ctx) sage: loads(dumps(a)) == a True
) |
Return the string representation of self.
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: ntl.GF2E([1,1,0,1], ctx) # indirect doctest [1 1 0 1]
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], ctx) ; y = ntl.GF2E([1,1,0,1,1], ctx) sage: x - y ## indirect doctest [0 1 1 1]
) |
Returns a FiniteFieldElement representation of this element. If a FiniteField k is provided it is constructed in this field if possible. A FiniteField will be constructed if none is provided.
Input:
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: e = ntl.GF2E([0,1], ctx) sage: a = e._sage_(); a a
Class: GF2EX
Functions: modulus_context
Special Functions: __add__,
__cmp__,
__init__,
__mul__,
__neg__,
__pow__,
__radd__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,1])) sage: f = ntl.GF2EX(ctx, '[[1 0] [2 1]]') sage: g = ntl.GF2EX(ctx, '[[1 0 1 1] [0 1 1 0 1] [1 0 1]]') sage: f+g ## indirect doctest [[0 0 1 1] [0 0 1 0 1] [1 0 1]]
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,1])) sage: f = ntl.GF2EX(ctx, '[[1 0] [2 1]]') sage: g = ntl.GF2EX(ctx, '[[1 0 1 1] [0 1 1 0 1] [1 0 1]]') sage: f*g ## indirect doctest [[1 0 1 1] [0 0 1 1] [1 0 0 1 0 1] [0 1 0 1]]
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,1])) sage: f = ntl.GF2EX(ctx, '[[1 0] [2 1]]') sage: -f ## indirect doctest [[1] [0 1]]
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,1])) sage: f = ntl.GF2EX(ctx, '[[1 0 1] [1 0 0 1] [1]]') sage: f == loads(dumps(f)) True
) |
Return the string representation of self.
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,1])) sage: ntl.GF2EX(ctx, '[[1 0] [2 1]]').__repr__() '[[1] [0 1]]'
) |
sage: ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,1])) sage: f = ntl.GF2EX(ctx, '[[1 0] [2 1]]') sage: g = ntl.GF2EX(ctx, '[[1 0 1 1] [0 1 1 0 1] [1 0 1]]') sage: f-g ## indirect doctest [[0 0 1 1] [0 0 1 0 1] [1 0 1]]
Class: GF2X
Functions: bin,
coeff,
ConstTerm,
deg,
diff,
DivRem,
GCD,
LeadCoeff,
list,
NumBits,
NumBytes,
reverse,
SetCoeff,
weight,
XGCD
) |
Returns binary representation of this element. It is
the same as setting ntl.GF2XHexOutput(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
) |
Return the coefficient of the monomial
in self.
Input:
sage: e = ntl.GF2X([0,1,0,1]) sage: e.coeff(0) 0 sage: e.coeff(1) 1
) |
Return the constant term of self.
sage: e = ntl.GF2X([1,0,1]) sage: e.ConstTerm() 1 sage: e = ntl.GF2X(0) sage: e.ConstTerm() 0
) |
Returns the degree of this polynomial
sage: ntl.GF2X([1,0,1,1]).deg() 3
) |
Differentiate self.
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.diff() [0 0 1]
) |
sage: a = ntl.GF2X(4) sage: a.DivRem( ntl.GF2X(2) ) ([0 1], []) sage: a.DivRem( ntl.GF2X(3) ) ([1 1], [1])
) |
Return gcd of self and other.
Input:
sage: a = ntl.GF2X(10) sage: b = ntl.GF2X(4) sage: a.GCD(b) [0 1]
) |
Return the leading coefficient of self. This is always 1 except when self == 0.
sage: e = ntl.GF2X([0,1]) sage: e.LeadCoeff() 1 sage: e = ntl.GF2X(0) sage: e.LeadCoeff() 0
) |
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
) |
returns number of bits of self, i.e., deg(self) + 1.
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.NumBits() 4
) |
Returns number of bytes of self, i.e., floor((NumBits(self)+7)/8)
sage: e = ntl.GF2X([1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1]) sage: e.NumBytes() 3
) |
Return reverse of a[0]..a[hi] (hi >= -1) hi defaults to deg(a)
Input:
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.reverse() [1 1 0 1]
) |
Return the constant term of self.
sage: e = ntl.GF2X([1,0,1]); e [1 0 1] sage: e.SetCoeff(1,1) sage: e [1 1 1]
) |
Return the number of nonzero coefficients in self.
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.weight() 3
) |
Return the extended gcd of self and other, i.e., elements r, s, t such that
r = s * self + t * other.
Input:
sage: a = ntl.GF2X(10) sage: b = ntl.GF2X(4) sage: r,s,t = a.XGCD(b) sage: r == a*s + t*b True
Special Functions: __add__,
__delitem__,
__div__,
__eq__,
__floordiv__,
__ge__,
__getitem__,
__gt__,
__hex__,
__init__,
__int__,
__le__,
__len__,
__lshift__,
__lt__,
__mod__,
__mul__,
__ne__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rfloordiv__,
__rlshift__,
__rmod__,
__rmul__,
__rpow__,
__rrshift__,
__rshift__,
__rsub__,
__setitem__,
__sub__,
_sage_
) |
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1,0]) sage: f + g ## indirect doctest [1 1 1 1]
) |
sage: a = ntl.GF2X(4) sage: a / ntl.GF2X(2) [0 1] sage: a / ntl.GF2X(3) Traceback (most recent call last): ... ArithmeticError: self (=[0 0 1]) is not divisible by b (=[1 1])
) |
sage: a = ntl.GF2X(4) sage: a // ntl.GF2X(2) [0 1] sage: a // ntl.GF2X(3) [1 1]
) |
sage: e = ntl.GF2X([0,1,0,1]) sage: e[0] # indirect doctest 0 sage: e[1] 1
) |
Returns hexadecimal representation of this element. It is
the same as setting ntl.GF2XHexOutput(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: hex(e) '0xb31'
Output: string representing this element in hexadecimal
) |
sage: e = ntl.GF2X([1,0,1,1,0]) sage: int(e) Traceback (most recent call last): ... ValueError: cannot convert non-constant polynomial to integer sage: e = ntl.GF2X([1]) sage: int(e) 1
) |
Return left shift of self by i bits ( == multiplication by
).
Input:
sage: a = ntl.GF2X(4); a [0 0 1] sage: a << 2 [0 0 0 0 1]
) |
sage: a = ntl.GF2X(4) sage: a % ntl.GF2X(2) [] sage: a % ntl.GF2X(3) [1]
) |
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1]) sage: f*g ## indirect doctest [0 1 0 1 1]
) |
sage: f = ntl.GF2X([1,0,1,1]) sage: -f ## indirect doctest [1 0 1 1] sage: f == -f True
) |
sage: f = ntl.GF2X(ntl.ZZ_pX([1,1,3],2)) sage: loads(dumps(f)) == f True sage: f = ntl.GF2X('0x1c') sage: loads(dumps(f)) == f True
) |
Return the string representation of self.
sage: ntl.GF2X(ntl.ZZ_pX([1,1,3],2)).__repr__() '[1 1 1]'
) |
Return right shift of self by i bits ( == floor division by
).
Input:
sage: a = ntl.GF2X(4); a [0 0 1] sage: a >> 1 [0 1]
) |
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1]) sage: f - g ## indirect doctest [1 1 1 1] sage: g - f [1 1 1 1]
) |
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:
sage: f = ntl.GF2X([1,0,1,1,0,1]) sage: f._sage_() x^5 + x^3 + x^2 + 1 sage: f._sage_(PolynomialRing(Integers(2),'y')) y^5 + y^3 + y^2 + 1
Class: mat_GF2E
Functions: determinant,
gauss,
image,
IsDiag,
IsIdent,
IsZero,
kernel,
list,
modulus_context,
NumCols,
NumRows,
transpose
) |
Returns the determinant.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2XHexOutput(0) sage: ntl.mat_GF2E(ctx, 5,5,[0..24]).determinant() [0 1 0 1 1 1 1] sage: ntl.mat_GF2E(ctx, 5,5,[3..27]).determinant() [0 1 1 0 0 1]
) |
Performs unitary row operations so as to bring this matrix
into row echelon form. If the optional argument ncols
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:
sage: m = ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: ntl.mat_GF2E(ctx, 5,5,[3..27]).gauss() 5 sage: ntl.mat_GF2E(ctx, 5,5).gauss() 0 sage: ntl.mat_GF2E(ctx, 5,5,[3..27]).gauss(3) 3
) |
The rows of X are computed as basis of A's row space. X is is row echelon form.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 3,3,[0..24]) sage: ntl.GF2XHexOutput(1) sage: m.image() [[0x3 0x4 0x5] [0x0 0x1 0x2] [0x0 0x0 0xc1] ]
) |
test if X is an n x n diagonal matrix with d on diagonal
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 3,3,[[0,1],0,0, 0,[0,1],0, 0,0,[0,1]]) sage: m.IsDiag(2, ntl.GF2E([0,1],ctx)) False sage: m.IsDiag(3, ntl.GF2E([0,1],ctx)) True
) |
test if A is the n x n identity matrix
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ~m sage: o = n*m sage: o.IsIdent() True
) |
Return True if self is zero, and false otherwise.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5) sage: m.IsZero() False sage: n.IsZero() True
) |
Computes a basis for the kernel of the map x -> x*A. where x is a row vector.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 3,3,[0..24]) sage: ntl.GF2XHexOutput(1) sage: m.kernel() []
) |
Returns a list of the entries in this matrix
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 2,2,[ntl.GF2E_random(ctx) for x in xrange(2*2)]) sage: ntl.GF2XHexOutput(0) sage: m.list() [[1 0 1 0 1 0 0 1], [1 0 1 1 1 0 0 1], [0 0 0 1 1 1 1], [1 1 1 1 1 1]]
) |
Returns the sturcture that holds the underlying NTL GF2E modulus.
sage: ntl.GF2XHexOutput(0) sage: ctx = ntl.GF2EContext( ntl.GF2X([1,1,0,1,1,0,0,0,1]) ) sage: a = ntl.GF2E(ntl.ZZ_pX([1,1,3],2), ctx) sage: A= ntl.mat_GF2E(ctx, 1, 1, [a]) sage: cty = A.modulus_context(); cty NTL modulus [1 1 0 1 1 0 0 0 1] sage: ctx == cty True
) |
Return the number of columns in self.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) ; m.NumCols() 5
) |
Return the number of rows in self.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) ; m.NumRows() 5
) |
Returns the transposed matrix of self.
Output: transposed Matrix
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = m.transpose() sage: n == m False sage: n.transpose() == m True
Special Functions: __add__,
__delitem__,
__eq__,
__ge__,
__getitem__,
__gt__,
__init__,
__invert__,
__le__,
__lt__,
__mul__,
__ne__,
__neg__,
__pow__,
__radd__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__,
_sage_
) |
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: m+n ## indirect doctest [[[1 1] [1 0 1] [1 1 1] [1 0 1] [1 1]] [[1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1] [1 0 1]] [[1 1 1] [1 0 1] [1 1] [1 0 1 1 1] [1 1 1 1 1]] [[1 0 1 1 1] [1 1] [1 0 1] [1 1 1] [1 0 1]] [[1 1] [1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1]] ]
) |
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: m[0,1] [1] sage: m[0,0] = 0 sage: m[0,0] []
) |
Return
; an error is raised if A is singular.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ~m sage: o = n*m sage: o.IsIdent() True
) |
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2XHexOutput(1) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: m*n ## indirect doctest [[0x87 0x04 0xc4 0xc7 0x87] [0x32 0x84 0x17 0x63 0x73] [0xa1 0x46 0x25 0xcd 0x2f] [0x1 0xcf 0xfb 0xd6 0x62] [0xcf 0x02 0x06 0xfd 0x79] ]
) |
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: -m == m ## indirect doctest True
) |
sage: k.<a> = GF(2^4) sage: ctx = ntl.GF2EContext(k) sage: A = ntl.mat_GF2E(ctx, 5,5, [0..24]) sage: A == loads(dumps(A)) True
) |
Return the string representation of self.
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2XHexOutput(1) sage: ntl.mat_GF2E(ctx, 2,2,range(4)).__repr__() '[[0x0 0x1] [0x0 0x1] ]' sage: ntl.GF2XHexOutput(0) sage: ntl.mat_GF2E(ctx, 2,2,range(4)).__repr__() '[[[] [1]] [[] [1]] ]'
) |
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: ntl.GF2XHexOutput(0) sage: m-n ## indirect doctest [[[1 1] [1 0 1] [1 1 1] [1 0 1] [1 1]] [[1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1] [1 0 1]] [[1 1 1] [1 0 1] [1 1] [1 0 1 1 1] [1 1 1 1 1]] [[1 0 1 1 1] [1 1] [1 0 1] [1 1 1] [1 0 1]] [[1 1] [1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1]] ]
) |
Returns a Matrix over a FiniteField representation of this element.
Input:
sage: ctx = ntl.GF2EContext([1,1,0,1]) sage: m = ntl.mat_GF2E(ctx, 2,2,[3..6]) sage: ntl.GF2XHexOutput(0) sage: m [[[1 1] [0 0 1]] [[1 0 1] [0 1 1]] ] sage: m._sage_() [ a + 1 a^2] [a^2 + 1 a^2 + a]
Class: mat_ZZ
Functions: charpoly,
determinant,
G_LLL_FP,
G_LLL_QP,
G_LLL_RR,
G_LLL_XD,
HNF,
list,
LLL,
LLL_FP,
LLL_QP,
LLL_RR,
LLL_XD,
ncols,
nrows
) |
Find the characteristic polynomial of self, and return it as an NTL ZZX.
sage: M = ntl.mat_ZZ(2,2,[1,2,3,4]) sage: M.charpoly() [-2 -5 1] sage: type(_) <type 'sage.libs.ntl.ntl_ZZX.ntl_ZZX'> sage: M.determinant() -2
) |
Return the determinant of self.
sage: ntl.mat_ZZ(8,8,[3..66]).determinant() 0 sage: ntl.mat_ZZ(2,5,range(10)).determinant() Traceback (most recent call last): ... TypeError: cannot take determinant of non-square matrix. sage: ntl.mat_ZZ(4,4,[next_prime(2**i) for i in range(16)]).determinant() -10248 sage: ntl.mat_ZZ(4,4,[ ZZ.random_element() for _ in range(16) ]).determinant() 678
) |
Peforms the same reduction as self.LLL_FP using the same calling conventions but uses the Givens Orthogonalization.
Givens Orthogonalization. This is a bit slower, but generally much more stable, and is really the preferred orthogonalization strategy. For a nice description of this, see Chapter 5 of [G. Golub and C. van Loan, Matrix Computations, 3rd edition, Johns Hopkins Univ. Press, 1996].
) |
Peforms the same reduction as self.G_LLL_FP using the same calling conventions but with quad float precision.
) |
Peforms the same reduction as self.G_LLL_FP using the same calling conventions but with aribitrary precision floating point numbers.
) |
Peforms the same reduction as self.G_LLL_FP using the same calling conventions but with extended exponent double precision.
) |
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: a = MatrixSpace(ZZ,200).random_element(x=-2, y=2) # -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: t = cputime(); d = A.determinant() sage: cputime(t) # random 0.33201999999999998 sage: t = cputime(); B = A.HNF(d) sage: cputime(t) # random 6.4924050000000006
In comparison, MAGMA does this much more quickly:
> A := MatrixAlgebra(IntegerRing(),200)![Random(-2,2) : i in [1..200^2]]; > time d := Determinant(A); Time: 0.140 > time H := HermiteForm(A); Time: 0.290
Also, PARI is also faster than NTL if one uses the flag 1 to the mathnf routine. The above takes 16 seconds in PARI.
TESTS:
sage: ntl.mat_ZZ(2,2,[1..4]).HNF() [ [1 0] [0 2] ]
) |
sage: m = ntl.mat_ZZ(3, 4, range(12)); m [ [0 1 2 3] [4 5 6 7] [8 9 10 11] ] sage: m.list() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
) |
Performs LLL reduction of self (puts self in an LLL form).
self is an m x n matrix, viewed as m rows of n-vectors. m may be less than, equal to, or greater than n, and the rows need not be linearly independent. self is transformed into an LLL-reduced basis, and the return value is the rank r of self so as det2 (see below). The first m-r rows of self are zero.
More specifically, elementary row transformations are
performed on self so that the non-zero rows of new-self form
an LLL-reduced basis for the lattice spanned by the rows of
old-self. The default reduction parameter is
,
which means that the squared length of the first non-zero
basis vector is no more than
times that of the
shortest vector in the lattice.
det2 is calculated as the square of the determinant of the lattice--note that sqrt(det2) is in general an integer only when r = n.
If return_U is True, a value U is returned which is the transformation matrix, so that U is a unimodular m x m matrix with U * old-self = new-self. Note that the first m-r rows of U form a basis (as a lattice) for the kernel of old-B.
The parameters a and b allow an arbitrary reduction parameter
, where
, where a and b are positive
integers. For a basis reduced with parameter delta, the
squared length of the first non-zero basis vector is no more
than
times that of the shortest vector in
the lattice.
The algorithm employed here is essentially the one in Cohen's book: [H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993]
Input:
sage: M=ntl.mat_ZZ(3,3,[1,2,3,4,5,6,7,8,9]) sage: M.LLL() (2, 54) sage: M [ [0 0 0] [2 1 0] [-1 1 3] ] sage: M=ntl.mat_ZZ(4,4,[-6,9,-15,-18,4,-6,10,12,10,-16,18,35,-24,36,-46,-82]); M [ [-6 9 -15 -18] [4 -6 10 12] [10 -16 18 35] [-24 36 -46 -82] ] sage: M.LLL() (3, 19140) sage: M [ [0 0 0 0] [0 -2 0 0] [-2 1 -5 -6] [0 -1 -7 5] ]
WARNING: This method modifies self. So after applying this method your matrix will be a vector of vectors.
) |
Performs approximate LLL reduction of self (puts self in an LLL form) subject to the following conditions:
The precision is double.
The return value is the rank of B.
Classical Gramm-Schmidt Orthogonalization is used:
This choice uses classical methods for computing the Gramm-Schmidt othogonalization. It is fast but prone to stability problems. This strategy was first proposed by Schnorr and Euchner [C. P. Schnorr and M. Euchner, Proc. Fundamentals of Computation Theory, LNCS 529, pp. 68-85, 1991]. The version implemented here is substantially different, improving both stability and performance.
If return_U is True, then also U is returned which is
the transition matrix:
The optional argument 'delta' is the reduction parameter, and may be set so that 0.50 <= delta < 1. Setting it close to 1 yields shorter vectors, and also improves the stability, but increases the running time. Recommended value: delta = 0.99.
The optional parameter 'verbose' can be set to see all kinds of fun things printed while the routine is executing. A status report is also printed every once in a while.
Input:
sage: M=ntl.mat_ZZ(3,3,[1,2,3,4,5,6,7,8,9]) sage: M.LLL_FP() 2 sage: M [ [0 0 0] [2 1 0] [-1 1 3] ] sage: M=ntl.mat_ZZ(4,4,[-6,9,-15,-18,4,-6,10,12,10,-16,18,35,-24,36,-46,-82]); M [ [-6 9 -15 -18] [4 -6 10 12] [10 -16 18 35] [-24 36 -46 -82] ] sage: M.LLL_FP() 3 sage: M [ [0 0 0 0] [0 -2 0 0] [-2 1 -5 -6] [0 -1 -7 5] ]
WARNING: This method modifies self. So after applying this method your matrix will be a vector of vectors.
) |
Peforms the same reduction as self.LLL_FP using the same calling conventions but with quad float precision.
) |
Peforms the same reduction as self.LLL_FP using the same calling conventions but with arbitrary precision floating point numbers.
) |
Peforms the same reduction as self.LLL_FP using the same calling conventions but with extended exponent double precision.
) |
Return the number of colunms in self.
sage: M = ntl.mat_ZZ(5,8,range(40)) sage: M.ncols() 8
) |
Return the number of rows in self.
sage: M = ntl.mat_ZZ(5,5,range(25)) sage: M.nrows() 5
Special Functions: __add__,
__cmp__,
__delitem__,
__getitem__,
__init__,
__mul__,
__pow__,
__radd__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__
) |
Return self + other.
sage: M = ntl.mat_ZZ(2,2,[8..11]) ; N = ntl.mat_ZZ(2,2,[-1..2]) sage: M+N [ [7 9] [11 13] ]
) |
sage: m = ntl.mat_ZZ(3, 2, range(6)) sage: m[0,0] ## indirect doctest 0 sage: m[2,1] 5 sage: m[3,2] # oops, 0 based Traceback (most recent call last): ... IndexError: array index out of range
) |
Multiply two matrices.
sage: M = ntl.mat_ZZ(2,2,[8..11]) ; N = ntl.mat_ZZ(2,2,[-1..2]) sage: M*N [ [1 18] [1 22] ]
) |
sage: m = ntl.mat_ZZ(3, 2, range(6)); m [ [0 1] [2 3] [4 5] ] sage: loads(dumps(m)) [ [0 1] [2 3] [4 5] ] sage: loads(dumps(m)) == m True
) |
Return the string representation of self.
sage: M = ntl.mat_ZZ(2,3,[5..10]) ; M.__repr__() '[ [5 6 7] [8 9 10] ]'
) |
Return self - other.
sage: M = ntl.mat_ZZ(2,2,[8..11]) ; N = ntl.mat_ZZ(2,2,[-1..2]) sage: M-N [ [9 9] [9 9] ]
Class: ZZ
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.
Functions: get_as_int_doctest,
get_as_sage_int,
set_from_int_doctest,
set_from_sage_int,
val_unit,
valuation
) |
This method exists solely for automated testing of get_as_int().
sage: x = ntl.ZZ(42) sage: i = x.get_as_int_doctest() sage: print i 42 sage: print type(i) <type 'int'>
) |
Gets the value as a sage int.
sage: n=ntl.ZZ(2983) sage: type(n.get_as_sage_int()) <type 'sage.rings.integer.Integer'>
Author: Joel B. Mohler
) |
This method exists solely for automated testing of set_from_int().
sage: x = ntl.ZZ() sage: x.set_from_int_doctest(42) sage: x 42
) |
Sets the value from a sage int.
sage: n=ntl.ZZ(2983) sage: n 2983 sage: n.set_from_sage_int(1234) sage: n 1234
Author: Joel B. Mohler
) |
Uses code in ntl_wrap.cpp to compute p-adic valuation and unit of self.
sage: a = ntl.ZZ(5^7*3^4) sage: p = ntl.ZZ(-5) sage: a.val_unit(p) (7, -81) sage: a.val_unit(ntl.ZZ(-3)) (4, 78125) sage: a.val_unit(ntl.ZZ(2)) (0, 6328125)
) |
Uses code in ntl_wrap.cpp to compute the number of times prime divides self.
sage: a = ntl.ZZ(5^7*3^4) sage: p = ntl.ZZ(5) sage: a.valuation(p) 7 sage: a.valuation(-p) 7
Special Functions: __add__,
__cmp__,
__init__,
__int__,
__mul__,
__neg__,
__pow__,
__radd__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__,
_integer_
) |
sage: n=ntl.ZZ(2983)+ntl.ZZ(2) sage: n 2985 sage: ntl.ZZ(23)+2 25
) |
Return self as an int.
sage: ntl.ZZ(22).__int__() 22 sage: type(ntl.ZZ(22).__int__()) <type 'int'>
sage: ntl.ZZ(10^30).__int__() 1000000000000000000000000000000L sage: type(ntl.ZZ(10^30).__int__()) <type 'long'>
) |
sage: n=ntl.ZZ(2983)*ntl.ZZ(2) sage: n 5966
) |
sage: x = ntl.ZZ(38) sage: -x -38 sage: x.__neg__() -38
) |
sage: from sage.libs.ntl.ntl_ZZ import ntl_ZZ sage: a = ntl_ZZ(-7) sage: loads(dumps(a)) -7
) |
Return the string representation of self.
sage: ntl.ZZ(5).__repr__() '5'
) |
sage: n=ntl.ZZ(2983)-ntl.ZZ(2) sage: n 2981 sage: ntl.ZZ(2983)-2 2981
) |
Gets the value as a sage int.
sage: n=ntl.ZZ(2983) sage: type(n._integer_()) <type 'sage.rings.integer.Integer'>
Alias for get_as_sage_int
Class: zz_p
NOTE: This type is provided mostly for completeness, and shouldn't be used in any production code.
Functions: clear,
is_one,
is_zero,
square
) |
Reset this element to 0.
sage: x = ntl.zz_p(5,102) ; x 5 sage: x.clear() ; x 0
) |
Return True exactly if this element is 1.
sage: f = ntl.zz_p(1,11) sage: f.is_one() True sage: f = ntl.zz_p(5,11) sage: f.is_one() False
) |
Return True exactly if this element is 0.
sage: f = ntl.zz_p(0,20) sage: f.is_zero() True sage: f = ntl.zz_p(1,20) sage: f.is_zero() False
) |
Return f*f.
sage: f = ntl.zz_p(15,23) sage: f*f 18
Special Functions: __add__,
__cmp__,
__div__,
__init__,
__int__,
__mul__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__
) |
sage: ntl.zz_p(5,23) + ntl.zz_p(6,23) 11
) |
sage: ntl.zz_p(5,23) / ntl.zz_p(2,23) 14
) |
Return self as an int.
sage: ntl.zz_p(3,next_prime(100)).__int__() 3 sage: int(ntl.zz_p(3,next_prime(100))) 3 sage: type(int(ntl.zz_p(3,next_prime(100)))) <type 'int'>
) |
sage: ntl.zz_p(5,23) * ntl.zz_p(6,23) 7
) |
Return the negative of self.
sage: f = ntl.zz_p(5,234) sage: -f ## indirect doctest 229
) |
For pickling.
TESTS:
sage: f = ntl.zz_p(16,244) sage: loads(dumps(f)) == f True
) |
Return the string representation of self.
sage: ntl.zz_p(3,79).__repr__() '3'
) |
sage: ntl.zz_p(5,23) - ntl.zz_p(6,23) 22
Class: ZZ_p
Objects of the class ZZ_p are represented as a ZZ
in the
range
.
Each ZZ_p contains a pointer of a ZZ_pContext which
contains pre-computed data for NTL. These can be explicitly constructed
and passed to the constructor of a ZZ_p or the ZZ_pContext
method ZZ_p
can be used to construct a ZZ_p element.
This class takes care of making sure that the C++ library NTL global variable is set correctly before performing any arithmetic.
Functions: lift,
modulus,
modulus_context
) |
Return a lift of self as an ntl.ZZ object.
sage: x = ntl.ZZ_p(8,18) sage: x.lift() 8 sage: type(x.lift()) <type 'sage.libs.ntl.ntl_ZZ.ntl_ZZ'>
) |
Returns the modulus as an NTL ZZ.
sage: c = ntl.ZZ_pContext(ntl.ZZ(20)) sage: n = ntl.ZZ_p(2983,c) sage: n.modulus() 20
) |
Return the modulus for self.
sage: x = ntl.ZZ_p(5,17) sage: c = x.modulus_context() sage: y = ntl.ZZ_p(3,c) sage: x+y 8 sage: c == y.modulus_context() True sage: c == ntl.ZZ_p(7,17).modulus_context() True
Special Functions: __add__,
__eq__,
__ge__,
__gt__,
__init__,
__int__,
__invert__,
__le__,
__lt__,
__mul__,
__ne__,
__neg__,
__pow__,
__radd__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__,
_get_as_int_doctest,
_integer_,
_sage_,
_set_from_int_doctest
) |
sage: x = ntl.ZZ_p(5,31) ; y = ntl.ZZ_p(8,31) sage: x+y ## indirect doctest 13
) |
Return self as an int.
sage: x = ntl.ZZ_p(3,8) sage: x.__int__() 3 sage: type(x.__int__()) <type 'int'>
) |
sage: c=ntl.ZZ_pContext(11) sage: ~ntl.ZZ_p(2r,modulus=c) 6
) |
sage: x = ntl.ZZ_p(5,31) ; y = ntl.ZZ_p(8,31) sage: x*y ## indirect doctest 9
) |
sage: x = ntl.ZZ_p(5,31) sage: -x ## indirect doctest 26
) |
sage: a = ntl.ZZ_p(4,7) sage: loads(dumps(a)) == a True
) |
Return the string representation of self.
sage: ntl.ZZ_p(7,192).__repr__() '7'
) |
sage: x = ntl.ZZ_p(5,31) ; y = ntl.ZZ_p(8,31) sage: x-y ## indirect doctest 28 sage: y-x 3
) |
This method exists solely for automated testing of get_as_int().
sage: c = ntl.ZZ_pContext(20) sage: x = ntl.ZZ_p(42,modulus=c) sage: i = x._get_as_int_doctest() sage: print i 2 sage: print type(i) <type 'int'>
) |
Return a lift of self as a SAGE integer.
sage: x = ntl.ZZ_p(8,188) sage: x._integer_() 8
sage: type(x._integer_()) <type 'sage.rings.integer.Integer'>
) |
Returns the value as a sage IntegerModRing.
sage: c = ntl.ZZ_pContext(20) sage: n = ntl.ZZ_p(2983, c) sage: type(n._sage_()) <type 'sage.rings.integer_mod.IntegerMod_int'> sage: n 3
Author: Joel B. Mohler
) |
This method exists solely for automated testing of set_from_int().
sage: c=ntl.ZZ_pContext(ntl.ZZ(20)) sage: x = ntl.ZZ_p(modulus=c) sage: x._set_from_int_doctest(42) sage: x 2 sage: x = ntl.ZZ_p(7,81) sage: x._set_from_int_doctest(int(3)) sage: x 3
Class: ZZ_pE
Objects of the class ZZ_pE are represented as a ZZ_pX
of
degree less than the degree of
.
Each ZZ_pE contains a pointer of a ZZ_pEContext which
contains pre-computed data for NTL. These can be explicitly constructed
and passed to the constructor of a ZZ_pE or the ZZ_pEContext
method ZZ_pE
can be used to construct a ZZ_pE element.
This class takes care of making sure that the C++ library NTL global variable is set correctly before performing any arithmetic.
Functions: get_as_ZZ_pX_doctest,
get_modulus_context,
modulus,
set_from_ZZ_pX_doctest
) |
This method exists solely for automated testing of get_as_ZZ_pX().
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) sage: x = ntl.ZZ_pE([42,1],modulus=c) sage: i = x.get_as_ZZ_pX_doctest() sage: print i [9 1] sage: print type(i) <type 'sage.libs.ntl.ntl_ZZ_pX.ntl_ZZ_pX'>
) |
Returns the modulus as an NTL ZZ_pX.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) sage: n=ntl.ZZ_pE([2983,233],c) sage: n.modulus() [1 1 1]
) |
This method exists solely for automated testing of set_from_ZZ_pX().
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1],11)) sage: x = ntl.ZZ_pE(modulus=c) sage: x.set_from_ZZ_pX_doctest(ntl.ZZ_pX([5,2,1],11)) sage: x [4 1]
Special Functions: __add__,
__eq__,
__ge__,
__gt__,
__init__,
__invert__,
__le__,
__lt__,
__mul__,
__ne__,
__neg__,
__pow__,
__radd__,
__reduce__,
__repr__,
__rmul__,
__rpow__,
__rsub__,
__sub__
) |
) |
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([2,7,1],11)) sage: ~ntl.ZZ_pE([1,1],modulus=c) [7 3]
) |
) |
) |
sage: a = ntl.ZZ_pE([4],ntl.ZZ_pX([1,1,1],ntl.ZZ(7))) sage: loads(dumps(a)) == a True
) |
) |
Class: ZZ_pEX
It can be used, for example, for arithmentic in
.
However, except where mathematically necessary (e.g., GCD computations),
ZZ_pE need not be a field.
Functions: clear,
constant_term,
convert_to_modulus,
copy,
degree,
derivative,
discriminant,
gcd,
get_modulus_context,
invert_and_truncate,
is_monic,
is_one,
is_x,
is_zero,
leading_coefficient,
left_shift,
list,
minpoly_mod,
multiply_and_truncate,
multiply_mod,
norm_mod,
preallocate_space,
quo_rem,
resultant,
reverse,
right_shift,
set_x,
square,
square_and_truncate,
trace_mod,
truncate,
xgcd
) |
Reset this polynomial to 0. Changes this polynomial in place.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f [[3 2] [1 2] [1 2]] sage: f.clear(); f []
) |
Return the constant coefficient of this polynomial.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.constant_term() [3 2]
) |
Returns a new ntl_ZZ_pX which is the same as self, but considered modulo a different p (but the SAME polynomial).
In order for this to make mathematical sense, c.p should divide self.c.p (in which case self is reduced modulo c.p) or self.c.p should divide c.p (in which case self is lifted to something modulo c.p congruent to self modulo self.c.p)
sage: c = ntl.ZZ_pEContext(ntl.ZZ_pX([-5, 0, 1], 5^20)) sage: a = ntl.ZZ_pE([192870, 1928189], c) sage: b = ntl.ZZ_pE([18275,293872987], c) sage: f = ntl.ZZ_pEX([a, b]) sage: g = f.convert_to_modulus(ntl.ZZ_pContext(ntl.ZZ(5^5))) sage: g [[2245 64] [2650 1112]] sage: g.get_modulus_context() NTL modulus [3120 0 1] (mod 3125) sage: g^2 [[1130 2985] [805 830] [2095 2975]] sage: (f^2).convert_to_modulus(ntl.ZZ_pContext(ntl.ZZ(5^5))) [[1130 2985] [805 830] [2095 2975]]
) |
Return a copy of self.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f [[3 2] [1 2] [1 2]] sage: y = f.copy() sage: y == f True sage: y is f False sage: f[0] = 0; y [[3 2] [1 2] [1 2]]
) |
Return the degree of this polynomial. The degree of the 0 polynomial is -1.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.degree() 2 sage: ntl.ZZ_pEX([], c).degree() -1
) |
Return the derivative of this polynomial.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.derivative() [[1 2] [2 4]]
) |
Return the discriminant of a=self, which is by definition
where m = deg(a), and lc(a) is the leading coefficient of a.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.discriminant() [1 6]
) |
Returns gcd(self, other) if we are working over a field.
NOTE: Does not work if p is not prime or if the modulus is not irreducible.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = f^2 sage: h = f^3 sage: g.gcd(h) [[2 1] [8 1] [9 1] [2] [1]] sage: f^2 [[5 8] [9 8] [6 8] [5] [8]] sage: eight = ntl.ZZ_pEX([[8]], c) sage: f^2 / eight [[2 1] [8 1] [9 1] [2] [1]]
) |
Returns the structure that holds the underlying NTL modulus.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.get_modulus_context() NTL modulus [1 1 1] (mod 7)
) |
Compute and return the inverse of self modulo
.
The constant term of self must be invertible.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = f.invert_and_truncate(5) sage: g [[8 6] [4 4] [5 9] [1 4] [0 1]] sage: f * g [[1] [] [] [] [] [2 8] [9 10]]
) |
Return True exactly if this polynomial is monic.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.is_monic() False sage: f = ntl.ZZ_pEX([a, b, 1], c) sage: f.is_monic() True
) |
Return True exactly if this polynomial is 1.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.is_one() False sage: f = ntl.ZZ_pEX([1, 0, 0], c) sage: f.is_one() True
) |
True if this is the polynomial "x".
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.is_x() False sage: f.set_x(); f.is_x() True
) |
Return True exactly if this polynomial is 0.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.is_zero() False sage: f = ntl.ZZ_pEX([0,0,7], c) sage: f.is_zero() True
) |
Return the leading coefficient of this polynomial.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.leading_coefficient() [1 2]
) |
Return the polynomial obtained by shifting all coefficients of this polynomial to the left n positions.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]); f [[3 2] [1 2] [1 2]] sage: f.left_shift(2) [[] [] [3 2] [1 2] [1 2]] sage: f.left_shift(5) [[] [] [] [] [] [3 2] [1 2] [1 2]]
A negative left shift is a right shift.
sage: f.left_shift(-2) [[1 2]]
) |
Return list of entries as a list of ntl_ZZ_pEs.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.list() [[3 2], [1 2], [1 2]]
) |
Return the minimal polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: m = ntl.ZZ_pEX([a - b, b^2, a, a*b]) sage: f.minpoly_mod(m) [[2 9] [8 2] [3 10] [1]]
) |
Return self*other but with terms of degree >= m removed.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([a - b, b^2, a, a*b]) sage: f*g [[6 4] [4 9] [4 6] [7] [1 9] [2 5]] sage: f.multiply_and_truncate(g, 3) [[6 4] [4 9] [4 6]]
) |
Return self*other deg(modulus) > 0, and self and other must have smaller degree.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([b^4, a*b^2, a - b]) sage: m = ntl.ZZ_pEX([a - b, b^2, a, a*b]) sage: f.multiply_mod(g, m) [[10 10] [4 4] [10 3]]
) |
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: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: m = ntl.ZZ_pEX([a - b, b^2, a, a*b]) sage: f.norm_mod(m) [9 2]
) |
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: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f[10]=ntl.ZZ_pE([1,8],c) # no new memory is allocated sage: f [[3 2] [1 2] [1 2] [] [] [] [] [] [] [] [1 8]]
) |
Given polynomials a, b in ZZ_pE[X], if p is prime and the defining modulus irreducible, there exist polynomials q, r in ZZ_pE[X] such that a = b*q + r, deg(r) < deg(b). This function returns (q, r).
If p is not prime or the modulus is not irreducible, this function may raise a RuntimeError due to division by a noninvertible element of ZZ_p.
sage: c = ntl.ZZ_pEContext(ntl.ZZ_pX([-5, 0, 1], 5^10)) sage: a = c.ZZ_pE([5, 1]) sage: b = c.ZZ_pE([4, 99]) sage: f = c.ZZ_pEX([a, b]) sage: g = c.ZZ_pEX([a^2, -b, a + b]) sage: g.quo_rem(f) ([[4947544 2492106] [4469276 6572944]], [[1864280 2123186]]) sage: f.quo_rem(g) ([], [[5 1] [4 99]])
) |
Return the resultant of self and other.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([a - b, b^2, a, a*b]) sage: f.resultant(g) [1] sage: (f*g).resultant(f^2) []
) |
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: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.reverse() [[1 2] [1 2] [3 2]] sage: f.reverse(hi=5) [[] [] [] [1 2] [1 2] [3 2]] sage: f.reverse(hi=1) [[1 2] [3 2]] sage: f.reverse(hi=-2) []
) |
Return the polynomial obtained by shifting all coefficients of this polynomial to the right n positions.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]); f [[3 2] [1 2] [1 2]] sage: f.right_shift(2) [[1 2]] sage: f.right_shift(5) []
A negative right shift is a left shift.
sage: f.right_shift(-5) [[] [] [] [] [] [3 2] [1 2] [1 2]]
) |
Set this polynomial to the monomial "x".
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f [[3 2] [1 2] [1 2]] sage: f.set_x(); f [[] [1]]
) |
Return
.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.square() [[5 1] [5 1] [2 1] [1] [4]]
) |
Return self*self but with terms of degree >= m removed.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f^2 [[5 8] [9 8] [6 8] [5] [8]] sage: f.square_and_truncate(3) [[5 8] [9 8] [6 8]]
) |
Return the trace of this polynomial modulo the modulus. The modulus must be monic, and of positive degree degree bigger than the degree of self.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: m = ntl.ZZ_pEX([a - b, b^2, a, a*b]) sage: f.trace_mod(m) [8 1]
) |
Return the truncation of this polynomial obtained by removing all terms of degree >= m.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f.truncate(3) [[3 2] [1 2] [1 2]] sage: f.truncate(1) [[3 2]]
) |
Returns r,s,t such that r = s*self + t*other.
Here r is the gcd of self and other.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 11)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([a-b, b^2, a]) sage: h = ntl.ZZ_pEX([a^2-b, b^4, b,a]) sage: r,s,t = (g*f).xgcd(h*f) sage: r [[4 6] [1] [1]] sage: f / ntl.ZZ_pEX([b]) [[4 6] [1] [1]] sage: s*f*g+t*f*h [[4 6] [1] [1]]
Special Functions: __add__,
__cmp__,
__copy__,
__delitem__,
__div__,
__getitem__,
__init__,
__mod__,
__mul__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rmod__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__
) |
Adds self and other.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([-b, a]) sage: f + g [[2] [4 4] [1 2]]
) |
Return a copy of self.
TEST:
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f [[3 2] [1 2] [1 2]] sage: y = f.copy() sage: y == f True sage: y is f False sage: f[0] = 0; y [[3 2] [1 2] [1 2]]
) |
Compute quotient self / other, if the quotient is a polynomial. Otherwise an Exception is raised.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a^2, -a*b-a*b, b^2]) sage: g = ntl.ZZ_pEX([-a, b]) sage: f / g [[4 5] [1 2]] sage: g / f Traceback (most recent call last): ... ArithmeticError: self (=[[4 5] [1 2]]) is not divisible by other (=[[5 1] [2 6] [4]])
) |
Returns the ith coefficient of self.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f[0] [3 2] sage: f[5] []
) |
Given polynomials a, b in ZZ_pE[X], if p is prime and the defining modulus irreducible, there exist polynomials q, r in ZZ_pE[X] such that a = b*q + r, deg(r) < deg(b). This function returns r.
If p is not prime or the modulus is not irreducible, this function may raise a RuntimeError due to division by a noninvertible element of ZZ_p.
sage: c = ntl.ZZ_pEContext(ntl.ZZ_pX([-5, 0, 1], 5^10)) sage: a = c.ZZ_pE([5, 1]) sage: b = c.ZZ_pE([4, 99]) sage: f = c.ZZ_pEX([a, b]) sage: g = c.ZZ_pEX([a^2, -b, a + b]) sage: g % f [[1864280 2123186]] sage: f % g [[5 1] [4 99]]
) |
Returns the product self * other.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([-b, a]) sage: f * g [[1 3] [1 1] [2 4] [6 4]] sage: c2 = ntl.ZZ_pEContext(ntl.ZZ_pX([4,1,1], 5)) # we can mix up the moduli sage: x = c2.ZZ_pEX([2,4]) sage: x^2 [[4] [1] [1]] sage: f * g # back to the first one and the ntl modulus gets reset correctly [[1 3] [1 1] [2 4] [6 4]]
) |
Return the negative of self.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: -f [[4 5] [6 5] [6 5]]
) |
TEST:
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: loads(dumps(f)) == f True
) |
Returns a string representation of self.
TEST:
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: f [[3 2] [1 2] [1 2]]
) |
Subtracts other from self.
sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], 7)) sage: a = ntl.ZZ_pE([3,2], c) sage: b = ntl.ZZ_pE([1,2], c) sage: f = ntl.ZZ_pEX([a, b, b]) sage: g = ntl.ZZ_pEX([-b, a]) sage: f - g [[4 4] [5] [1 2]]
Class: ZZ_pX
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,
convert_to_modulus,
copy,
degree,
derivative,
discriminant,
factor,
gcd,
get_modulus_context,
invert_and_truncate,
invmod,
invmod_newton,
is_monic,
is_one,
is_x,
is_zero,
leading_coefficient,
left_shift,
linear_roots,
list,
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: c=ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,0,3],c) sage: mod = ntl.ZZ_pX([-5,2,0,0,1],c) sage: f.charpoly_mod(mod) [11 1 8 14 1]
) |
Reset this polynomial to 0. Changes this polynomial in place.
sage: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,3],c) sage: f [1 2 3] sage: f.clear() sage: f []
) |
Return the constant coefficient of this polynomial.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([3,6,9],c) sage: f.constant_term() 3 sage: f = ntl.ZZ_pX([],c) sage: f.constant_term() 0
) |
Returns a new ntl_ZZ_pX which is the same as self, but considered modulo a different p.
In order for this to make mathematical sense, c.p should divide self.c.p (in which case self is reduced modulo c.p) or self.c.p should divide c.p (in which case self is lifted to something modulo c.p congruent to self modulo self.c.p)
sage: a = ntl.ZZ_pX([412,181,991],5^4) sage: a [412 181 366] sage: b = ntl.ZZ_pX([198,333,91],5^4) sage: ap = a.convert_to_modulus(ntl.ZZ_pContext(5^2)) sage: bp = b.convert_to_modulus(ntl.ZZ_pContext(5^2)) sage: ap [12 6 16] sage: bp [23 8 16] sage: ap*bp [1 9 8 24 6] sage: (a*b).convert_to_modulus(ntl.ZZ_pContext(5^2)) [1 9 8 24 6]
) |
Return a copy of self.
sage: x = ntl.ZZ_pX([0,5,-3],11) sage: y = x.copy() sage: x == y True sage: x is y False sage: x[0] = 4; y [0 5 8]
) |
Return the degree of this polynomial. The degree of the 0 polynomial is -1.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([5,0,1],c) sage: f.degree() 2 sage: f = ntl.ZZ_pX(range(100),c) sage: f.degree() 99 sage: f = ntl.ZZ_pX([], c) sage: f.degree() -1 sage: f = ntl.ZZ_pX([1],c) sage: f.degree() 0
) |
Return the derivative of this polynomial.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,7,0,13],c) 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: c = ntl.ZZ_pContext(ntl.ZZ(17)) sage: f = ntl.ZZ_pX([1,2,0,3],c) sage: f.discriminant() 1
) |
Return the factorization of self. Assumes self is monic.
NOTE: The roots are returned in a random order.
These computations use pseudo-random numbers, so we set the seed for reproducible testing.
sage: set_random_seed(0) sage: ntl.ZZ_pX([-1,0,0,0,0,1],5).factor() [([4 1], 5)] sage: ls = ntl.ZZ_pX([-1,0,0,0,1],5).factor() sage: ls [([4 1], 1), ([2 1], 1), ([1 1], 1), ([3 1], 1)] sage: prod( [ x[0] for x in ls ] ) [4 0 0 0 1] sage: ntl.ZZ_pX([3,7,0,1], 31).factor() [([3 7 0 1], 1)] sage: ntl.ZZ_pX([3,7,1,8], 28).factor() Traceback (most recent call last): ... ValueError: self must be monic.
) |
Return the gcd d = gcd(a, b), where by convention the leading coefficient of d is >= 0. We uses a multi-modular algorithm.
sage: c=ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,3],c) * ntl.ZZ_pX([4,5],c)**2 sage: g = ntl.ZZ_pX([1,1,1],c)**3 * ntl.ZZ_pX([1,2,3],c) sage: f.gcd(g) [6 12 1] sage: g.gcd(f) [6 12 1]
) |
Return the modulus for self.
sage: x = ntl.ZZ_pX([0,5,3],17) sage: c = x.get_modulus_context() sage: y = ntl.ZZ_pX([5],c) sage: x+y [5 5 3]
) |
Compute and return the inverse of self modulo
.
The constant term of self must be a unit.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,3,4,5,6,7],c) 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]
) |
Returns the inverse of self modulo the modulus using ntl's InvMod.
) |
Returns the inverse of self modulo the modulus using Newton lifting. Only works if modulo a power of a prime, and if modulus is either unramified or Eisenstein.
) |
Return True exactly if this polynomial is monic.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([2,0,0,1],c) sage: f.is_monic() True sage: g = f.reverse() sage: g.is_monic() False sage: g [1 0 0 2] sage: f = ntl.ZZ_pX([1,2,0,3,0,2],c) sage: f.is_monic() False
) |
Return True exactly if this polynomial is 1.
sage: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,1],c) sage: f.is_one() False sage: f = ntl.ZZ_pX([1],c) sage: f.is_one() True
) |
True if this is the polynomial "x".
sage: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([],c) sage: f.set_x() sage: f.is_x() True sage: f = ntl.ZZ_pX([0,1],c) sage: f.is_x() True sage: f = ntl.ZZ_pX([1],c) sage: f.is_x() False
) |
Return True exactly if this polynomial is 0.
sage: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([0,0,0,20],c) sage: f.is_zero() True sage: f = ntl.ZZ_pX([0,0,1],c) sage: f [0 0 1] sage: f.is_zero() False
) |
Return the leading coefficient of this polynomial.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([3,6,9],c) sage: f.leading_coefficient() 9 sage: f = ntl.ZZ_pX([],c) sage: f.leading_coefficient() 0
) |
Return the polynomial obtained by shifting all coefficients of this polynomial to the left n positions.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([2,0,0,1],c) 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) roots. Returns the list of roots.
NOTE: This function will go into an infinite loop if you give it a polynomial without deg(f) linear factors. Note also that the result is not deterministic, i.e. the order of the roots returned is random.
sage: ntl.ZZ_pX([-1,0,0,0,0,1],5).linear_roots() [1, 1, 1, 1, 1] sage: roots = ntl.ZZ_pX([-1,0,0,0,1],5).linear_roots() sage: [ ntl.ZZ_p(i,5) in roots for i in [1..4] ] [True, True, True, True] sage: ntl.ZZ_pX([3,7,1,8], 28).linear_roots() Traceback (most recent call last): ... ValueError: self must be monic.
) |
Return list of entries as a list of ntl_ZZ_p.
sage: x = ntl.ZZ_pX([1,3,5],11) sage: x.list() [1, 3, 5] sage: type(x.list()[0]) <type 'sage.libs.ntl.ntl_ZZ_p.ntl_ZZ_p'>
) |
Return the minimal polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self.
sage: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([0,0,1],c) 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: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,3,4,5],c) sage: g = ntl.ZZ_pX([10],c) 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: c = ntl.ZZ_pContext(ntl.ZZ(20)) sage: modulus = ntl.ZZ_pX([1,2,0,1],c) # must be monic sage: g = ntl.ZZ_pX([-1,0,1],c) sage: h = ntl.ZZ_pX([3,7,13],c) 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: c=ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,0,3],c) sage: mod = ntl.ZZ_pX([-5,2,0,0,1],c) 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: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,3],c) 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: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX(range(10), c); g = ntl.ZZ_pX([-1,0,1], c) 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: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([17,0,1,1],c) sage: g = ntl.ZZ_pX([34,-17,18,2],c) 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: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,3,4,5],c) 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: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([2,0,0,1],c) 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: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([],c) sage: f.set_x() sage: f [0 1] sage: g = ntl.ZZ_pX([0,1],c) 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: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([-1,0,1], c) sage: f*f [1 0 15 0 1]
) |
Return self*self but with terms of degree >= m removed.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,3,4,5],c) 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: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,0,3,0,1],c) sage: f.trace_list() [5, 0, 14, 0, 10]
The input polynomial must be monic or a ValueError is raised:
sage: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,0,3,0,2],c) 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 degree of self.
sage: c=ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,0,3],c) sage: mod = ntl.ZZ_pX([5,3,-1,1,1],c) sage: f.trace_mod(mod) 3
) |
Return the truncation of this polynomial obtained by removing all terms of degree >= m.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([1,2,3,4,5],c) 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: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,3],c) * ntl.ZZ_pX([4,5],c)**2 sage: g = ntl.ZZ_pX([1,1,1],c)**3 * ntl.ZZ_pX([1,2,3],c) 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],c) sage: g = ntl.ZZ_pX([18,0,1],c) sage: f.xgcd(g) ([1], [13], [4])
Special Functions: __add__,
__cmp__,
__copy__,
__delitem__,
__div__,
__getitem__,
__init__,
__mod__,
__mul__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rmod__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__,
_getitem_as_int_doctest,
_left_pshift,
_right_pshift,
_setitem_from_int_doctest
) |
sage: c = ntl.ZZ_pContext(20) sage: ntl.ZZ_pX(range(5),c) + ntl.ZZ_pX(range(6),c) [0 2 4 6 8 5]
) |
Return a copy of self.
sage: x = ntl.ZZ_pX([0,5,-3],11) sage: y = x.copy() sage: x == y True sage: x is y False sage: x[0] = 4; y [0 5 8]
) |
Compute quotient self / other, if the quotient is a polynomial. Otherwise an Exception is raised.
sage: c = ntl.ZZ_pContext(17) sage: f = ntl.ZZ_pX([1,2,3], c) * ntl.ZZ_pX([4,5], c)**2 sage: g = ntl.ZZ_pX([4,5], c) sage: f/g [4 13 5 15] sage: ntl.ZZ_pX([1,2,3],c) * ntl.ZZ_pX([4,5],c) [4 13 5 15]
sage: f = ntl.ZZ_pX(range(10), c); g = ntl.ZZ_pX([-1,0,1], c) sage: f/g Traceback (most recent call last): ... ArithmeticError: self (=[0 1 2 3 4 5 6 7 8 9]) is not divisible by other (=[16 0 1])
) |
Returns the ith entry of self.
sage: c = ntl.ZZ_pContext(20) sage: x = ntl.ZZ_pX([2, 3, 4], c) sage: x[1] 3
) |
Given polynomials a, b in ZZ_p[X], if p is prime, then there exist polynomials q, r in ZZ_p[X] such that a = b*q + r, deg(r) < deg(b). This function returns r.
If p is not prime this function may raise a RuntimeError due to division by a noninvertible element of ZZ_p.
sage: c = ntl.ZZ_pContext(ntl.ZZ(17)) sage: f = ntl.ZZ_pX([2,4,6], c); g = ntl.ZZ_pX([2], c) sage: f % g # 0 []
sage: f = ntl.ZZ_pX(range(10), c); g = ntl.ZZ_pX([-1,0,1], c) sage: f % g [3 8]
) |
sage: c1 = ntl.ZZ_pContext(20) sage: alpha = ntl.ZZ_pX(range(5), c1) sage: beta = ntl.ZZ_pX(range(6), c1) sage: alpha * beta [0 0 1 4 10 0 10 14 11] sage: c2 = ntl.ZZ_pContext(ntl.ZZ(5)) # we can mix up the moduli sage: x = ntl.ZZ_pX([2, 3, 4], c2) sage: x^2 [4 2 0 4 1] sage: alpha * beta # back to the first one and the ntl modulus gets reset correctly [0 0 1 4 10 0 10 14 11]
) |
Return the negative of self.
sage: c = ntl.ZZ_pContext(20) sage: f = ntl.ZZ_pX([2,0,0,1],c) sage: -f [18 0 0 19]
) |
TEST:
sage: f = ntl.ZZ_pX([1,2,3,7], 5); f [1 2 3 2] sage: loads(dumps(f)) == f True
) |
Return the string representation of self.
sage: x = ntl.ZZ_pX([1,0,8],5) sage: x [1 0 3] sage: x.__repr__() '[1 0 3]'
) |
sage: c = ntl.ZZ_pContext(20) sage: ntl.ZZ_pX(range(5),c) - ntl.ZZ_pX(range(6),c) [0 0 0 0 0 15]
) |
This method exists solely for automated testing of getitem_as_int().
sage: c = ntl.ZZ_pContext(20) sage: x = ntl.ZZ_pX([2, 3, 5, -7, 11], c) sage: i = x._getitem_as_int_doctest(3) sage: print i 13 sage: print type(i) <type 'int'> sage: print x._getitem_as_int_doctest(15) 0
) |
Multiplies all coefficients by n and the context by n.
) |
Divides all coefficients by n and the context by n. Only really makes sense when n divides self.c.p
) |
This method exists solely for automated testing of setitem_from_int().
sage: c = ntl.ZZ_pContext(20) sage: x = ntl.ZZ_pX([2, 3, 4], c) sage: x._setitem_from_int_doctest(5, 42) sage: x [2 3 4 0 0 2]
Class: zz_pX
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: clear,
constant_term,
degree,
diff,
invert_and_truncate,
is_monic,
is_one,
is_x,
is_zero,
leading_coefficient,
list,
multiply_and_truncate,
preallocate_space,
quo_rem,
reverse,
set_x,
square,
square_and_truncate,
truncate
) |
Reset this polynomial to 0. Changes this polynomial in place.
sage: f = ntl.zz_pX([1,2,3],17) sage: f [1, 2, 3] sage: f.clear() sage: f []
) |
Return the constant coefficient of this polynomial.
sage: f = ntl.zz_pX([3,6,9],127) sage: f.constant_term() 3 sage: f = ntl.zz_pX([], 12223) sage: f.constant_term() 0
) |
Return the degree of this polynomial. The degree of the 0 polynomial is -1.
sage: f = ntl.zz_pX([5,0,1],50) sage: f.degree() 2 sage: f = ntl.zz_pX(range(100),50) sage: f.degree() 99 sage: f = ntl.zz_pX([],10) sage: f.degree() -1 sage: f = ntl.zz_pX([1],77) sage: f.degree() 0
) |
The formal derivative of self.
sage: f = ntl.zz_pX(range(10), 17) sage: f.diff() [1, 4, 9, 16, 8, 2, 15, 13, 13]
) |
Compute and return the inverse of self modulo
.
The constant term of self must be 1 or -1.
sage: f = ntl.zz_pX([1,2,3,4,5,6,7],20) 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: f = ntl.zz_pX([2,0,0,1],17) sage: f.is_monic() True sage: g = f.reverse() sage: g.is_monic() False sage: g [1, 0, 0, 2] sage: f = ntl.zz_pX([1,2,0,3,0,2],717) sage: f.is_monic() False
) |
Return True exactly if this polynomial is 1.
sage: f = ntl.zz_pX([1,1],101) sage: f.is_one() False sage: f = ntl.zz_pX([1],2) sage: f.is_one() True
) |
True if this is the polynomial "x".
sage: f = ntl.zz_pX([],100) sage: f.set_x() sage: f.is_x() True sage: f = ntl.zz_pX([0,1],383) sage: f.is_x() True sage: f = ntl.zz_pX([1],38) sage: f.is_x() False
) |
Return True exactly if this polynomial is 0.
sage: f = ntl.zz_pX([0,0,0,20],5) sage: f.is_zero() True sage: f = ntl.zz_pX([0,0,1],30) sage: f [0, 0, 1] sage: f.is_zero() False
) |
Return the leading coefficient of this polynomial.
sage: f = ntl.zz_pX([3,6,9],19) sage: f.leading_coefficient() 9 sage: f = ntl.zz_pX([],21) sage: f.leading_coefficient() 0
) |
Return list of entries as a list of python ints.
sage: f = ntl.zz_pX([23, 5,0,1], 10) sage: f.list() [3, 5, 0, 1] sage: type(f.list()[0]) <type 'int'>
) |
Return self*other but with terms of degree >= m removed.
sage: f = ntl.zz_pX([1,2,3,4,5],20) sage: g = ntl.zz_pX([10],20) sage: f.multiply_and_truncate(g, 2) [10] sage: g.multiply_and_truncate(f, 2) [10]
) |
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.zz_pX([1,2,3],17) 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 quotient and remander when self is devided by right.
Specifically, this return r, q such that
sage: f = ntl.zz_pX(range(7), 19) sage: g = ntl.zz_pX([2,4,6], 19) sage: f // g [1, 1, 15, 16, 1] sage: f % g [17, 14] sage: f.quo_rem(g) ([1, 1, 15, 16, 1], [17, 14]) sage: (f // g) * g + f % g [0, 1, 2, 3, 4, 5, 6]
) |
Returns self with coefficients reversed, i.e.
.
sage: f = ntl.zz_pX([2,4,6], 17) sage: f.reverse() [6, 4, 2]
) |
Set this polynomial to the monomial "x".
sage: f = ntl.zz_pX([],177) sage: f.set_x() sage: f [0, 1] sage: g = ntl.zz_pX([0,1],177) 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.zz_pX([-1,0,1],17) sage: f*f [1, 0, 15, 0, 1]
) |
Return self*self but with terms of degree >= m removed.
sage: f = ntl.zz_pX([1,2,3,4,5],20) sage: f.square_and_truncate(4) [1, 4, 10] sage: (f*f).truncate(4) [1, 4, 10]
) |
Return the truncation of this polynomial obtained by removing all terms of degree >= m.
sage: f = ntl.zz_pX([1,2,3,4,5],70) 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) []
Special Functions: __add__,
__cmp__,
__delitem__,
__div__,
__floordiv__,
__getitem__,
__init__,
__lshift__,
__mod__,
__mul__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rfloordiv__,
__rlshift__,
__rmod__,
__rmul__,
__rpow__,
__rrshift__,
__rshift__,
__rsub__,
__setitem__,
__sub__
) |
Return self + other.
sage: ntl.zz_pX(range(5),20) + ntl.zz_pX(range(6),20) ## indirect doctest [0, 2, 4, 6, 8, 5] sage: ntl.zz_pX(range(5),20) + ntl.zz_pX(range(6),50) Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus.
) |
Compute quotient self / other, if the quotient is a polynomial. Otherwise an Exception is raised.
sage: f = ntl.zz_pX([1,2,3],17) * ntl.zz_pX([4,5],17)**2 sage: g = ntl.zz_pX([4,5],17) sage: f/g ## indirect doctest [4, 13, 5, 15] sage: ntl.zz_pX([1,2,3],17) * ntl.zz_pX([4,5],17) [4, 13, 5, 15]
sage: f = ntl.zz_pX(range(10),17); g = ntl.zz_pX([-1,0,1],17) sage: f/g Traceback (most recent call last): ... ArithmeticError: self (=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) is not divisible by other (=[16, 0, 1]) sage: ntl.zz_pX(range(5),20) / ntl.zz_pX(range(6),50) Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus.
) |
Returns the whole part of
.
sage: f = ntl.zz_pX(range(10), 19); g = ntl.zz_pX([1]*5, 19) sage: f // g ## indirect doctest [8, 18, 18, 18, 18, 9]
) |
Return the ith coefficient of f.
sage: f = ntl.zz_pX(range(7), 71) sage: f[3] ## indirect doctest 3
sage: f[-5] 0
sage: f[27] 0
) |
Shifts this polynomial to the left, which is multiplication by
.
sage: f = ntl.zz_pX([2,4,6], 17) sage: f << 2 ## indirect doctest [0, 0, 2, 4, 6]
) |
Given polynomials a, b in ZZ[X], there exist polynomials q, r in QQ[X] such that a = b*q + r, deg(r) < deg(b). This function returns q if q lies in ZZ[X], and otherwise raises an Exception.
sage: f = ntl.zz_pX([2,4,6],17); g = ntl.zz_pX([2],17) sage: f % g ## indirect doctest []
sage: f = ntl.zz_pX(range(10),17); g = ntl.zz_pX([-1,0,1],17) sage: f % g [3, 8]
) |
sage: ntl.zz_pX(range(5),20) * ntl.zz_pX(range(6),20) ## indirect doctest [0, 0, 1, 4, 10, 0, 10, 14, 11] sage: ntl.zz_pX(range(5),20) * ntl.zz_pX(range(6),50) Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus.
) |
Return the negative of self.
sage: f = ntl.zz_pX([2,0,0,1],20) sage: -f [18, 0, 0, 19]
) |
TESTS:
sage: f = ntl.zz_pX([10,10^30+1], 20) sage: f == loads(dumps(f)) True
) |
Return the string representation of self.
sage: f = ntl.zz_pX([3,5], 17) sage: f.__repr__() '[3, 5]'
) |
Shifts this polynomial to the right, which is division by
(and truncation).
sage: f = ntl.zz_pX([1,2,3], 17) sage: f >> 2 ## indirect doctest [3]
) |
Return self - other.
sage: ntl.zz_pX(range(5),32) - ntl.zz_pX(range(6),32) [0, 0, 0, 0, 0, 27] sage: ntl.zz_pX(range(5),20) - ntl.zz_pX(range(6),50) ## indirect doctest Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus.
Class: ZZX
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,
getitem_as_int_doctest,
invert_and_truncate,
is_monic,
is_one,
is_x,
is_zero,
lcm,
leading_coefficient,
left_shift,
list,
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,
setitem_from_int_doctest,
square,
square_and_truncate,
squarefree_decomposition,
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 proof=None, see
proof.polynomial or sage.structure.proof, but the global
default is proof=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 a copy of self.
sage: x = ntl.ZZX([1,32]) sage: y = x.copy() sage: y == x True sage: y is x False
) |
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 proof=None, see proof.polynomial or sage.structure.proof, but the global default is proof=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]
) |
This method exists solely for automated testing of getitem_as_int().
sage: x = ntl.ZZX([2, 3, 5, -7, 11]) sage: i = x.getitem_as_int_doctest(3) sage: print i -7 sage: print type(i) <type 'int'> sage: print x.getitem_as_int_doctest(15) 0
) |
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.
sage: x1 = ntl.ZZX([-1,0,0,1]) sage: x2 = ntl.ZZX([-1,0,0,0,0,0,1]) sage: x1.lcm(x2) [-1 0 0 0 0 0 1]
) |
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]
) |
Retrieves coefficients as a list of ntl.ZZ Integers.
sage: x = ntl.ZZX([129381729371289371237128318293718237, 2, -3, 0, 4]) sage: L = x.list(); L [129381729371289371237128318293718237, 2, -3, 0, 4] sage: type(L[0]) <type 'sage.libs.ntl.ntl_ZZ.ntl_ZZ'> sage: x = ntl.ZZX() sage: L = x.list(); L []
) |
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=None, see proof.polynomial or sage.structure.proof, but
the global 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=None, see proof.polynomial or sage.structure.proof,
but the global default is 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
) |
This method exists solely for automated testing of setitem_from_int().
sage: x = ntl.ZZX([2, 3, 4]) sage: x.setitem_from_int_doctest(5, 42) sage: x [2 3 4 0 0 42]
) |
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]
) |
Returns the square-free decomposition of self (a partial factorization into square-free, relatively prime polynomials) as a list of 2-tuples, where the first element in each tuple is a factor, and the second is its exponent. Assumes that self is primitive.
sage: f = ntl.ZZX([0, 1, 2, 1]) sage: f.squarefree_decomposition() [([0 1], 1), ([1 1], 2)]
) |
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 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 not 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
errors with probability no more than
. The default is
default is proof=None, see proof.polynomial or sage.structure.proof,
but the global default is True), then this function may use a
randomized strategy that errors 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__,
__copy__,
__delitem__,
__div__,
__getitem__,
__init__,
__mod__,
__mul__,
__neg__,
__pow__,
__radd__,
__rdiv__,
__reduce__,
__repr__,
__rmod__,
__rmul__,
__rpow__,
__rsub__,
__setitem__,
__sub__
) |
sage: ntl.ZZX(range(5)) + ntl.ZZX(range(6)) [0 2 4 6 8 5]
) |
Return a copy of self.
sage: x = ntl.ZZX([1,32]) sage: y = x.copy() sage: y == x True sage: y is x False
) |
Compute quotient self / other, if the quotient is a polynomial. Otherwise an Exception is raised.
sage: f = ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])**2 sage: g = ntl.ZZX([4,5]) sage: f/g [4 13 22 15] sage: ntl.ZZX([1,2,3]) * ntl.ZZX([4,5]) [4 13 22 15]
sage: f = ntl.ZZX(range(10)); g = ntl.ZZX([-1,0,1]) sage: f/g Traceback (most recent call last): ... ArithmeticError: self (=[0 1 2 3 4 5 6 7 8 9]) is not divisible by other (=[-1 0 1])
) |
Retrieves coefficient number i as an NTL ZZ.
sage: x = ntl.ZZX([129381729371289371237128318293718237, 2, -3, 0, 4]) sage: x[0] 129381729371289371237128318293718237 sage: type(x[0]) <type 'sage.libs.ntl.ntl_ZZ.ntl_ZZ'> sage: x[1] 2 sage: x[2] -3 sage: x[3] 0 sage: x[4] 4 sage: x[5] 0
) |
Given polynomials a, b in ZZ[X], there exist polynomials q, r in QQ[X] such that a = b*q + r, deg(r) < deg(b). This function returns q if q lies in ZZ[X], and otherwise raises an Exception.
sage: f = ntl.ZZX([2,4,6]); g = ntl.ZZX([2]) sage: f % g # 0 []
sage: f = ntl.ZZX(range(10)); g = ntl.ZZX([-1,0,1]) sage: f % g [20 25]
) |
sage: ntl.ZZX(range(5)) * ntl.ZZX(range(6)) [0 0 1 4 10 20 30 34 31 20]
) |
Return the negative of self.
sage: f = ntl.ZZX([2,0,0,1]) sage: -f [-2 0 0 -1]
) |
sage: from sage.libs.ntl.ntl_ZZX import ntl_ZZX sage: f = ntl_ZZX([1,2,0,4]) sage: loads(dumps(f)) == f True
) |
Return the string representation of self.
sage: ntl.ZZX([1,3,0,5]).__repr__() '[1 3 0 5]'
) |
sage: ntl.ZZX(range(5)) - ntl.ZZX(range(6)) [0 0 0 0 0 -5]
See About this document... for information on suggesting changes.