15.2 Victor Shoup's NTL C++ Library

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

GF2EContext( )

Create a new GF2EContext.

sage: c = ntl.GF2EContext(GF(2^2,'a'))
sage: n1 = ntl.GF2E([0,1],c)
sage: n1
[0 1]

GF2E_random( )

Returns a random element from GF2E modulo the current modulus.

Input:

ctx
- the GF2E context for which an random element should be created

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]

GF2XHexOutput( )

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]

ZZ_pContext( )

Create a new ZZ_pContext.

sage: c = ntl.ZZ_pContext(178)
sage: n1 = ntl.ZZ_p(212,c)
sage: n1
34

ZZ_pEContext( )

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)

ZZ_p_random( )

Return a random number modulo p.

sage: sage.libs.ntl.ntl_ZZ_p.ntl_ZZ_p_random_element(17)
8

ZZ_random( )

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)

ZZ_random_bits( )

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

sage: [ntl.ZZ_random_bits(20) for i in range(3)]
[564629, 843071, 972038]

Author: Didier Deshommes (dfdeshom@gmail.com)

ntl_setSeed( )

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

zz_pContext( )

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

class GF2
The GF2 represents the field GF(2). Computationally speaking, it is not a particularly useful class. Its main use is to make the interfaces to the various finite field classes as uniform as possible.

Special Functions: __add__,$ \,$ __div__,$ \,$ __eq__,$ \,$ __ge__,$ \,$ __gt__,$ \,$ __init__,$ \,$ __int__,$ \,$ __le__,$ \,$ __lt__,$ \,$ __mul__,$ \,$ __ne__,$ \,$ __neg__,$ \,$ __pow__,$ \,$ __radd__,$ \,$ __rdiv__,$ \,$ __reduce__,$ \,$ __repr__,$ \,$ __rmul__,$ \,$ __rpow__,$ \,$ __rsub__,$ \,$ __sub__

__add__( )

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

__div__( )

sage: o = ntl.GF2(1)
sage: z = ntl.GF2(0)
sage: o/o
1
sage: o/z
Traceback (most recent call last):
...
ZeroDivisionError

__int__( )

Return self as an int.

sage: o = ntl.GF2(1)
sage: z = ntl.GF2(0)
sage: int(z)
0
sage: int(o)
1

__mul__( )

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

__neg__( )

sage: o = ntl.GF2(1)
sage: z = ntl.GF2(0)
sage: -z
0
sage: -o
1

__reduce__( )

Serializes self.

sage: a = ntl.GF2(1)
sage: loads(dumps(a))
1

__repr__( )

Return the string representation of self.

sage: str(ntl.GF2(1)) # indirect doctest
'1'

__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

Class: GF2E

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

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

IsOne( )

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

IsZero( )

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

list( )

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

modulus_context( )

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

rep( )

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

trace( )

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_

__add__( )

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]

__copy__( )

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

__div__( )

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]

__mul__( )

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]

__neg__( )

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]

__reduce__( )

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

__repr__( )

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]

__sub__( )

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]

_sage_( )

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:

k
- optional GF(2**deg)

Output: FiniteFieldElement over k

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

class GF2EX
Minimal wrapper of NTL's GF2EX class.

Functions: modulus_context

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

__add__( )

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

__mul__( )

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

__neg__( )

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

__reduce__( )

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

__repr__( )

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

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

Class: GF2X

class GF2X
Univariate Polynomials over GF(2) via NTL.

Functions: bin,$ \,$ coeff,$ \,$ ConstTerm,$ \,$ deg,$ \,$ diff,$ \,$ DivRem,$ \,$ GCD,$ \,$ LeadCoeff,$ \,$ list,$ \,$ NumBits,$ \,$ NumBytes,$ \,$ reverse,$ \,$ SetCoeff,$ \,$ weight,$ \,$ XGCD

bin( )

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

coeff( )

Return the coefficient of the monomial $ X^i$ in self.

Input:

i
- degree of X

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

ConstTerm( )

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

deg( )

Returns the degree of this polynomial

sage: ntl.GF2X([1,0,1,1]).deg()
3

diff( )

Differentiate self.

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

DivRem( )

sage: a = ntl.GF2X(4)
sage: a.DivRem( ntl.GF2X(2) )
([0 1], [])
sage: a.DivRem( ntl.GF2X(3) )
([1 1], [1])

GCD( )

Return gcd of self and other.

Input:

other
- ntl.GF2X

sage: a = ntl.GF2X(10)
sage: b = ntl.GF2X(4)
sage: a.GCD(b)
[0 1]

LeadCoeff( )

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

list( )

Represents this element as a list of binary digits.

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

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

NumBits( )

returns number of bits of self, i.e., deg(self) + 1.

sage: e = ntl.GF2X([1,0,1,1,0])
sage: e.NumBits()
4

NumBytes( )

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

reverse( )

Return reverse of a[0]..a[hi] (hi >= -1) hi defaults to deg(a)

Input:

hi
- bit position until which reverse is requested

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

SetCoeff( )

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]

weight( )

Return the number of nonzero coefficients in self.

sage: e = ntl.GF2X([1,0,1,1,0])
sage: e.weight()
3

XGCD( )

Return the extended gcd of self and other, i.e., elements r, s, t such that

r = s * self + t * other.

Input:

other
- ntl.GF2X

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_

__add__( )

sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1,0])
sage: f + g ## indirect doctest
[1 1 1 1]

__div__( )

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

__floordiv__( )

sage: a = ntl.GF2X(4)
sage: a // ntl.GF2X(2)
[0 1]
sage: a // ntl.GF2X(3)
[1 1]

__getitem__( )

sage: e = ntl.GF2X([0,1,0,1])
sage: e[0] # indirect doctest
0
sage: e[1]
1

__hex__( )

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

__int__( )

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

__lshift__( )

Return left shift of self by i bits ( == multiplication by $ X^i$ ).

Input:

i
- offset/power of X

sage: a = ntl.GF2X(4); a
[0 0 1]
sage: a << 2
[0 0 0 0 1]

__mod__( )

sage: a = ntl.GF2X(4)
sage: a % ntl.GF2X(2)
[]
sage: a % ntl.GF2X(3)
[1]

__mul__( )

sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1])
sage: f*g ## indirect doctest
[0 1 0 1 1]

__neg__( )

sage: f = ntl.GF2X([1,0,1,1])
sage: -f ## indirect doctest
[1 0 1 1]
sage: f == -f
True

__reduce__( )

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

__repr__( )

Return the string representation of self.

sage: ntl.GF2X(ntl.ZZ_pX([1,1,3],2)).__repr__()
'[1 1 1]'

__rshift__( )

Return right shift of self by i bits ( == floor division by $ X^i$ ).

Input:

i
- offset/power of X

sage: a = ntl.GF2X(4); a
[0 0 1]
sage: a >> 1
[0 1]

__sub__( )

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]

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

Output: polynomial in R

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

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

Functions: determinant,$ \,$ gauss,$ \,$ image,$ \,$ IsDiag,$ \,$ IsIdent,$ \,$ IsZero,$ \,$ kernel,$ \,$ list,$ \,$ modulus_context,$ \,$ NumCols,$ \,$ NumRows,$ \,$ transpose

determinant( )

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]

gauss( )

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:

ncols
- number of columns to process (default: all)

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

image( )

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

IsDiag( )

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

IsIdent( )

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

IsZero( )

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

kernel( )

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()
[]

list( )

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

modulus_context( )

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

NumCols( )

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

NumRows( )

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

transpose( )

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_

__add__( )

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

__getitem__( )

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

__invert__( )

Return $ X = A^{-1}$ ; 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

__mul__( )

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

__neg__( )

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

__reduce__( )

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

__repr__( )

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

__sub__( )

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

_sage_( )

Returns a Matrix over a FiniteField representation of this element.

Input:

self
- mat_GF2E element
k
- optional GF(2**deg)

Output: Matrix over k

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

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

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

charpoly( )

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

determinant( )

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

G_LLL_FP( )

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

G_LLL_QP( )

Peforms the same reduction as self.G_LLL_FP using the same calling conventions but with quad float precision.

G_LLL_RR( )

Peforms the same reduction as self.G_LLL_FP using the same calling conventions but with aribitrary precision floating point numbers.

G_LLL_XD( )

Peforms the same reduction as self.G_LLL_FP using the same calling conventions but with extended exponent double precision.

HNF( )

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

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

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

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

sage: 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]
]

list( )

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]

LLL( )

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 $ \delta=3/4$ , which means that the squared length of the first non-zero basis vector is no more than $ 2^{r-1}$ 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 $ \delta=a/b$ , where $ 1/4 < a/b \leq 1$ , 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 $ 1/(delta-1/4)^{r-1}$ 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:

a
- parameter a as described above (default: 3)
b
- parameter b as described above (default: 4)
return_U
- return U as described above
verbose
- if True NTL will produce some verbatim messages on what's going on internally (default: False)

Output: (rank,det2,[U]) where rank,det2, and U are as described above and U is an optional return value if return_U is True.

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.

LLL_FP( )

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: $ U * self_{old} = self_{new}$

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:

delta
- as described above (0.5 <= delta < 1.0) (default: 0.75)
return_U
- return U as described above
verbose
- if True NTL will produce some verbatim messages on what's going on internally (default: False)

Output: (rank,[U]) where rank and U are as described above and U is an optional return value if return_U is True.

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.

LLL_QP( )

Peforms the same reduction as self.LLL_FP using the same calling conventions but with quad float precision.

LLL_RR( )

Peforms the same reduction as self.LLL_FP using the same calling conventions but with arbitrary precision floating point numbers.

LLL_XD( )

Peforms the same reduction as self.LLL_FP using the same calling conventions but with extended exponent double precision.

ncols( )

Return the number of colunms in self.

sage: M = ntl.mat_ZZ(5,8,range(40))
sage: M.ncols()
8

nrows( )

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__

__add__( )

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

__getitem__( )

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

__mul__( )

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

__reduce__( )

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

__repr__( )

Return the string representation of self.

            sage: M = ntl.mat_ZZ(2,3,[5..10]) ; M.__repr__()
            '[
[5 6 7]
[8 9 10]
]'

__sub__( )

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

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

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

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

Functions: get_as_int_doctest,$ \,$ get_as_sage_int,$ \,$ set_from_int_doctest,$ \,$ set_from_sage_int,$ \,$ val_unit,$ \,$ valuation

get_as_int_doctest( )

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

get_as_sage_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

set_from_int_doctest( )

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

set_from_sage_int( )

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

val_unit( )

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)

valuation( )

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_

__add__( )

sage: n=ntl.ZZ(2983)+ntl.ZZ(2)
sage: n
2985
sage: ntl.ZZ(23)+2
25

__int__( )

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

__mul__( )

sage: n=ntl.ZZ(2983)*ntl.ZZ(2)
sage: n
5966

__neg__( )

sage: x = ntl.ZZ(38)
sage: -x
-38
sage: x.__neg__()
-38

__reduce__( )

sage: from sage.libs.ntl.ntl_ZZ import ntl_ZZ
sage: a = ntl_ZZ(-7)
sage: loads(dumps(a))
-7

__repr__( )

Return the string representation of self.

sage: ntl.ZZ(5).__repr__()
'5'

__sub__( )

sage: n=ntl.ZZ(2983)-ntl.ZZ(2)
sage: n
2981
sage: ntl.ZZ(2983)-2
2981

_integer_( )

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

class zz_p
The class zz_p implements arithmetic modulo $ p$ , for p smaller than a machine word.

NOTE: This type is provided mostly for completeness, and shouldn't be used in any production code.

Functions: clear,$ \,$ is_one,$ \,$ is_zero,$ \,$ square

clear( )

Reset this element to 0.

sage: x = ntl.zz_p(5,102) ; x
5
sage: x.clear() ; x
0

is_one( )

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

is_zero( )

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

square( )

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__

__add__( )

sage: ntl.zz_p(5,23) + ntl.zz_p(6,23)
11

__div__( )

sage: ntl.zz_p(5,23) / ntl.zz_p(2,23)
14

__int__( )

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

__mul__( )

sage: ntl.zz_p(5,23) * ntl.zz_p(6,23)
7

__neg__( )

Return the negative of self.

sage: f = ntl.zz_p(5,234)
sage: -f ## indirect doctest
229

__reduce__( )

For pickling.

TESTS:

sage: f = ntl.zz_p(16,244)
sage: loads(dumps(f)) == f
True

__repr__( )

Return the string representation of self.

sage: ntl.zz_p(3,79).__repr__()
'3'

__sub__( )

sage: ntl.zz_p(5,23) - ntl.zz_p(6,23)
22

Class: ZZ_p

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

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

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

lift( )

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

modulus( )

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

modulus_context( )

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

__add__( )

sage: x = ntl.ZZ_p(5,31) ; y = ntl.ZZ_p(8,31)
sage: x+y ## indirect doctest
13

__int__( )

Return self as an int.

sage: x = ntl.ZZ_p(3,8)
sage: x.__int__()
3
sage: type(x.__int__())
<type 'int'>

__invert__( )

sage: c=ntl.ZZ_pContext(11)
sage: ~ntl.ZZ_p(2r,modulus=c)
6

__mul__( )

sage: x = ntl.ZZ_p(5,31) ; y = ntl.ZZ_p(8,31)
sage: x*y ## indirect doctest
9

__neg__( )

sage: x = ntl.ZZ_p(5,31)
sage: -x ## indirect doctest
26

__reduce__( )

sage: a = ntl.ZZ_p(4,7)
sage: loads(dumps(a)) == a
True

__repr__( )

Return the string representation of self.

sage: ntl.ZZ_p(7,192).__repr__()
'7'

__sub__( )

sage: x = ntl.ZZ_p(5,31) ; y = ntl.ZZ_p(8,31)
sage: x-y ## indirect doctest
28
sage: y-x
3

_get_as_int_doctest( )

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

_integer_( )

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

_sage_( )

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

_set_from_int_doctest( )

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

class ZZ_pE
The ZZ_pE class is used to model $ \mathbf{Z}/ p\mathbf{Z}[x] / (f(x))$ . The modulus $ p$ may be any positive integer, not necessarily prime, and the modulus f is not required to be irreducible.

Objects of the class ZZ_pE are represented as a ZZ_pX of degree less than the degree of $ f$ .

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

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

modulus( )

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]

set_from_ZZ_pX_doctest( )

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__

__add__( )

__invert__( )

sage: c=ntl.ZZ_pEContext(ntl.ZZ_pX([2,7,1],11))
sage: ~ntl.ZZ_pE([1,1],modulus=c)
[7 3]

__mul__( )

__neg__( )

__reduce__( )

sage: a = ntl.ZZ_pE([4],ntl.ZZ_pX([1,1,1],ntl.ZZ(7)))
sage: loads(dumps(a)) == a
True

__repr__( )

__sub__( )

Class: ZZ_pEX

class ZZ_pEX
The class ZZ_pEX implements polynomials over finite ring extensions of $ \mathbf{Z}/ p\mathbf{Z}$ .

It can be used, for example, for arithmentic in $ GF(p^n)[X]$ . 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

clear( )

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

constant_term( )

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]

convert_to_modulus( )

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

copy( )

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

degree( )

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

derivative( )

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

discriminant( )

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

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

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

sage: 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]

gcd( )

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

get_modulus_context( )

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)

invert_and_truncate( )

Compute and return the inverse of self modulo $ x^m$ . 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]]

is_monic( )

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

is_one( )

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

is_x( )

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

is_zero( )

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

leading_coefficient( )

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]

left_shift( )

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

list( )

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

minpoly_mod( )

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

multiply_and_truncate( )

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

multiply_mod( )

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

norm_mod( )

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

sage: 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]

preallocate_space( )

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

sage: 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]]

quo_rem( )

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

resultant( )

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

reverse( )

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

sage: 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)
[]

right_shift( )

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

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

square( )

Return $ f^2$ .

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

square_and_truncate( )

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

trace_mod( )

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]

truncate( )

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

xgcd( )

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__

__add__( )

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

__copy__( )

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

__div__( )

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

__getitem__( )

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

__mod__( )

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

__mul__( )

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

__neg__( )

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

__reduce__( )

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

__repr__( )

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

__sub__( )

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

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

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

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

Functions: charpoly_mod,$ \,$ clear,$ \,$ constant_term,$ \,$ 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

charpoly_mod( )

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]

clear( )

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

constant_term( )

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

convert_to_modulus( )

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]

copy( )

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]

degree( )

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

derivative( )

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]

discriminant( )

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

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

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

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

factor( )

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.

gcd( )

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

sage: 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]

get_modulus_context( )

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]

invert_and_truncate( )

Compute and return the inverse of self modulo $ x^m$ . 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]

invmod( )

Returns the inverse of self modulo the modulus using ntl's InvMod.

invmod_newton( )

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.

is_monic( )

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

is_one( )

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

is_x( )

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

is_zero( )

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

leading_coefficient( )

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

left_shift( )

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]

linear_roots( )

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.

list( )

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

minpoly_mod( )

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 $ f^2 = 0$ moduluo $ g$ , its minimal polynomial is of degree $ 2$ .

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

multiply_and_truncate( )

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

sage: 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]

multiply_mod( )

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]

norm_mod( )

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

sage: 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]

preallocate_space( )

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

sage: 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]

quo_rem( )

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

resultant( )

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

reverse( )

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

sage: 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)
[]

right_shift( )

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

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

square( )

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]

square_and_truncate( )

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]

trace_list( )

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

sage: 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.

trace_mod( )

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

truncate( )

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

xgcd( )

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

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

sage: 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

__add__( )

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]

__copy__( )

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]

__div__( )

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

__getitem__( )

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

__mod__( )

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]

__mul__( )

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]

__neg__( )

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]

__reduce__( )

TEST:

sage: f = ntl.ZZ_pX([1,2,3,7], 5); f
[1 2 3 2]
sage: loads(dumps(f)) == f
True

__repr__( )

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

__sub__( )

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]

_getitem_as_int_doctest( )

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

_left_pshift( )

Multiplies all coefficients by n and the context by n.

_right_pshift( )

Divides all coefficients by n and the context by n. Only really makes sense when n divides self.c.p

_setitem_from_int_doctest( )

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

class zz_pX
The class zz_pX implements polynomial arithmetic modulo $ p$ , for p smaller than a machine word.

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

clear( )

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

constant_term( )

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

degree( )

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

diff( )

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]

invert_and_truncate( )

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

sage: f = ntl.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]

is_monic( )

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

is_one( )

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

is_x( )

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

is_zero( )

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

leading_coefficient( )

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

list( )

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

multiply_and_truncate( )

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]

preallocate_space( )

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

sage: f = ntl.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]

quo_rem( )

Returns the quotient and remander when self is devided by right.

Specifically, this return r, q such that $ self = q * right + r$

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]

reverse( )

Returns self with coefficients reversed, i.e. $ x^n self(x^{-n})$ .

sage: f = ntl.zz_pX([2,4,6], 17)
sage: f.reverse()
[6, 4, 2]

set_x( )

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

square( )

Return f*f.

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

square_and_truncate( )

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]

truncate( )

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__

__add__( )

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.

__div__( )

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.

__floordiv__( )

Returns the whole part of $ self / right$ .

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]

__getitem__( )

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

__lshift__( )

Shifts this polynomial to the left, which is multiplication by $ x^n$ .

sage: f = ntl.zz_pX([2,4,6], 17)
sage: f << 2 ## indirect doctest
[0, 0, 2, 4, 6]

__mod__( )

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]

__mul__( )

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.

__neg__( )

Return the negative of self.

sage: f = ntl.zz_pX([2,0,0,1],20)
sage: -f
[18, 0, 0, 19]

__reduce__( )

TESTS:

sage: f = ntl.zz_pX([10,10^30+1], 20)
sage: f == loads(dumps(f))
True

__repr__( )

Return the string representation of self.

sage: f = ntl.zz_pX([3,5], 17)
sage: f.__repr__()
'[3, 5]'

__rshift__( )

Shifts this polynomial to the right, which is division by $ x^n$ (and truncation).

sage: f = ntl.zz_pX([1,2,3], 17)
sage: f >> 2 ## indirect doctest
[3]

__sub__( )

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

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

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

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

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

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

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

Functions: charpoly_mod,$ \,$ clear,$ \,$ constant_term,$ \,$ content,$ \,$ copy,$ \,$ degree,$ \,$ derivative,$ \,$ discriminant,$ \,$ gcd,$ \,$ 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

charpoly_mod( )

Return the characteristic polynomial of this polynomial modulo the modulus. The modulus must be monic of degree bigger than self. If proof=False (the default is 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 $ 2^{-80}$ .

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

clear( )

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

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

constant_term( )

Return the constant coefficient of this polynomial.

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

content( )

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

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

copy( )

Return a copy of self.

sage: x = ntl.ZZX([1,32])
sage: y = x.copy()
sage: y == x
True
sage: y is x
False

degree( )

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

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

derivative( )

Return the derivative of this polynomial.

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

discriminant( )

Return the discriminant of self, which is by definition

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

where m = deg(a), and lc(a) is the leading coefficient of a. If proof is False (the default is 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 $ 2^{-80}$ .

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

gcd( )

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

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

getitem_as_int_doctest( )

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

invert_and_truncate( )

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

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

is_monic( )

Return True exactly if this polynomial is monic.

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

is_one( )

Return True exactly if this polynomial is 1.

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

is_x( )

True if this is the polynomial "x".

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

is_zero( )

Return True exactly if this polynomial is 0.

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

lcm( )

Return the least common multiple of self and other.

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]

leading_coefficient( )

Return the leading coefficient of this polynomial.

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

left_shift( )

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

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

A negative left shift is a right shift.

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

list( )

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

minpoly_mod_noproof( )

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

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

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

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

multiply_and_truncate( )

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

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

multiply_mod( )

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

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

norm_mod( )

Return the norm of this polynomial modulo the modulus. The modulus must be monic, and of positive degree strictly greater than the degree of self. If proof=False (the default is proof=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 $ 2^{-80}$ .

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

The norm is the constant term of the characteristic polynomial.

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

preallocate_space( )

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

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

primitive_part( )

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

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

pseudo_quo_rem( )

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

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

quo_rem( )

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

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

resultant( )

Return the resultant of self and other. If proof = False (the default is proof=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 $ 2^{-80}$ .

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

reverse( )

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

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

right_shift( )

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

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

set_x( )

Set this polynomial to the monomial "x".

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

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

sage: f is g
False

setitem_from_int_doctest( )

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]

square( )

Return f*f.

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

square_and_truncate( )

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

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

squarefree_decomposition( )

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

trace_list( )

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

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

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

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

trace_mod( )

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

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

truncate( )

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

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

xgcd( )

If self and other are coprime over the rationals, return r, s, t such that r = s*self + t*other. Otherwise return 0. This is 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 $ 2^{-80}$ . 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 $ 2^{-80}$ .

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

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

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

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

__add__( )

sage: ntl.ZZX(range(5)) + ntl.ZZX(range(6))
[0 2 4 6 8 5]

__copy__( )

Return a copy of self.

sage: x = ntl.ZZX([1,32])
sage: y = x.copy()
sage: y == x
True
sage: y is x
False

__div__( )

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

__getitem__( )

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

__mod__( )

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]

__mul__( )

sage: ntl.ZZX(range(5)) * ntl.ZZX(range(6))
[0 0 1 4 10 20 30 34 31 20]

__neg__( )

Return the negative of self.

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

__reduce__( )

sage: from sage.libs.ntl.ntl_ZZX import ntl_ZZX
sage: f = ntl_ZZX([1,2,0,4])
sage: loads(dumps(f)) == f
True

__repr__( )

Return the string representation of self.

sage: ntl.ZZX([1,3,0,5]).__repr__()
'[1 3 0 5]'

__sub__( )

sage: ntl.ZZX(range(5)) - ntl.ZZX(range(6))
[0 0 0 0 0 -5]

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