Dense univariate polynomials over \ZZ/n\ZZ, implemented using FLINT.

This module gives a fast implementation of (\ZZ/n\ZZ)[x] whenever n is at most sys.maxint. We use it by default in preference to NTL when the modulus is small, falling back to NTL if the modulus is too large, as in the example below.

EXAMPLES:

sage: R.<a> = PolynomialRing(Integers(100))
sage: type(a)
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
sage: R.<a> = PolynomialRing(Integers(5*2^64))
sage: type(a)
<type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_ZZ'>
sage: R.<a> = PolynomialRing(Integers(5*2^64), implementation="FLINT")
...
ValueError: FLINT does not support modulus 92233720368547758080

AUTHORS:

  • Burcin Erocal (2008-11) initial implementation
  • Martin Albrecht (2009-01) another initial implementation
class sage.rings.polynomial.polynomial_zmod_flint.Polynomial_template

Template for interfacing to external C / C++ libraries for implementations of polynomials.

AUTHORS:

  • Robert Bradshaw (2008-10): original idea for templating
  • Martin Albrecht (2008-10): initial implementation

This file implements a simple templating engine for linking univariate polynomials to their C/C++ library implementations. It requires a ‘linkage’ file which implements the celement_ functions (see sage.libs.ntl.ntl_GF2X_linkage for an example). Both parts are then plugged together by inclusion of the linkage file when inheriting from this class. See sage.rings.polynomial.polynomial_gf2x for an example.

We illustrate the generic glueing using univariate polynomials over \mathop{\mathrm{GF}}(2).

Note

Implementations using this template MUST implement coercion from base ring elements and __getitem__. See Polynomial_GF2X for an example.

__copy__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: copy(x) is x
False
sage: copy(x) == x
True
__eq__()
x.__eq__(y) <==> x==y
__floordiv__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x//(x + 1)
1
sage: (x + 1)//x
1
__ge__()
x.__ge__(y) <==> x>=y
__getslice__()

x.__getslice__(i, j) <==> x[i:j]

Use of negative indices is not supported.

__gt__()
x.__gt__(y) <==> x>y
__hash__()
x.__hash__() <==> hash(x)
__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__int__()
x.__int__() <==> int(x)
__le__()
x.__le__(y) <==> x<=y
__long__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: int(x)
...
ValueError: Cannot coerce polynomial with degree 1 to integer.

sage: int(P(1))
1
__lshift__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: f = x^3 + x^2 + 1
sage: f << 1
x^4 + x^3 + x
__lt__()
x.__lt__(y) <==> x<y
__mod__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: (x^2 + 1) % x^2
1
__ne__()
x.__ne__(y) <==> x!=y
__neg__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: -x
x
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
__nonzero__()
x.__nonzero__() <==> x != 0
__pow__()
x.__pow__(y[, z]) <==> pow(x, y[, z])
__reduce__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: loads(dumps(x)) == x
True
__rfloordiv__()
x.__rfloordiv__(y) <==> y//x
__rlshift__()
x.__rlshift__(y) <==> y<<x
__rmod__()
x.__rmod__(y) <==> y%x
__rpow__()
y.__rpow__(x[, z]) <==> pow(x, y[, z])
__rrshift__()
x.__rrshift__(y) <==> y>>x
__rshift__()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x>>1
1
sage: (x^2 + x)>>1
x + 1
sage: (x^2 + x) >> -1 
x^3 + x^2 
_add_()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x + 1
x + 1
_derivative()

Returns the formal derivative of self with respect to var.

var must be either the generator of the polynomial ring to which this polynomial belongs, or None (either way the behaviour is the same).

See also

derivative()

EXAMPLES:

sage: R.<x> = Integers(77)[]
sage: f = x^4 - x - 1
sage: f._derivative()
4*x^3 + 76
sage: f._derivative(None)
4*x^3 + 76

sage: f._derivative(2*x)
...
ValueError: cannot differentiate with respect to 2*x

sage: y = var("y")
sage: f._derivative(y)
...
ValueError: cannot differentiate with respect to y
_mul_()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x*(x+1)
x^2 + x
_singular_()

Return Singular representation of this polynomial

INPUT:

  • singular – Singular interpreter (default: default interpreter)
  • have_ring – set to True if the ring was already set in Singular

EXAMPLE:

sage: P.<x> = PolynomialRing(GF(7))
sage: f = 3*x^2 + 2*x + 5
sage: singular(f)
3*x^2+2*x-2
_sub_()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x - 1
x + 1
degree()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x.degree()
1
sage: P(1).degree()
0
sage: P(0).degree()
-1
gcd()

Return the greatest common divisor of self and other.

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: f = x*(x+1)
sage: f.gcd(x+1)
x + 1
sage: f.gcd(x^2)
x
is_gen()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x.is_gen()
True
sage: (x+1).is_gen()
False
is_one()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: P(1).is_one()
True
is_zero()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x.is_zero()
False
list()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: x.list()
[0, 1]
sage: list(x)
[0, 1]
quo_rem()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: f = x^2 + x + 1
sage: f.quo_rem(x + 1)
(x, 1)
shift()

EXAMPLE:

sage: P.<x> = GF(2)[]
sage: f = x^3 + x^2 + 1
sage: f.shift(1)
x^4 + x^3 + x
sage: f.shift(-1)
x^2 + x
truncate()

Returns this polynomial mod x^n.

EXAMPLES:

sage: R.<x> =GF(2)[]
sage: f = sum(x^n for n in range(10)); f
x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
sage: f.truncate(6)
x^5 + x^4 + x^3 + x^2 + x + 1
xgcd()

Computes extended gcd of self and other.

EXAMPLE:

sage: P.<x> = GF(7)[]
sage: f = x*(x+1)
sage: f.xgcd(x+1)
(x + 1, 0, 1)
sage: f.xgcd(x^2)
(x, 1, 6)
class sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint
__call__()

Evaluate polynomial at x=a.

INPUT: either

  • a – ring element; need not be in the coefficient ring of the polynomial.
  • a dictionary for kwds:value pairs. If the variable name of the polynomial is a keyword it is substituted in; otherwise this polynomial is returned unchanged.

EXAMPLE:

sage: P.<x> = PolynomialRing(GF(7))
sage: f= x^2 + 1
sage: f(0)
1
sage: f(2)
5
sage: f(3)
3
__getitem__()

EXAMPLE:

sage: P.<x> = GF(32003)[]
sage: f = 24998*x^2 + 29761*x + 2252
sage: f[100]
0
sage: f[1]
29761
sage: f[0]
2252
sage: f[-1]
0
__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
_mul_zn_poly()

Returns the product of two polynomials using the zn_poly library.

See http://www.math.harvard.edu/~dmharvey/zn_poly/ for details on zn_poly.

INPUT:

  • self: Polynomial
  • right: Polynomial (over same base ring as self)

OUTPUT: (Polynomial) the product self*right.

EXAMPLE:

sage: P.<x> = PolynomialRing(GF(next_prime(2^30)))
sage: f = P.random_element(1000)
sage: g = P.random_element(1000)
sage: f*g == f._mul_zn_poly(g)
True

sage: P.<x> = PolynomialRing(Integers(100))
sage: P
Univariate Polynomial Ring in x over Ring of integers modulo 100
sage: r = (10*x)._mul_zn_poly(10*x); r
0
sage: r.degree()
-1

ALGORITHM:

uses David Harvey’s zn_poly library.

NOTE: This function is a technology preview. It might disappear or be replaced without a deprecation warning.

_unsafe_mutate()

Never use this unless you really know what you are doing.

INPUT:

  • n – degree
  • value – coefficient

Warning

This could easily introduce subtle bugs, since Sage assumes everywhere that polynomials are immutable. It’s OK to use this if you really know what you’re doing.

EXAMPLES:

sage: R.<x> = GF(7)[]
sage: f = (1+2*x)^2; f
4*x^2 + 4*x + 1
sage: f._unsafe_mutate(1, -5)
sage: f
4*x^2 + 2*x + 1
resultant()

Returns the resultant of self and other, which must lie in the same polynomial ring.

INPUT:

  • other – a polynomial

OUTPUT: an element of the base ring of the polynomial ring

EXAMPLES:

sage: R.<x> = GF(19)['x']
sage: f = x^3 + x + 1;  g = x^3 - x - 1
sage: r = f.resultant(g); r
11
sage: r.parent() is GF(19)
True
small_roots()

See sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots() for the documentation of this function.

EXAMPLE:

sage: N = 10001
sage: K = Zmod(10001)
sage: P.<x> = PolynomialRing(K)
sage: f = x^3 + 10*x^2 + 5000*x - 222
sage: f.small_roots()
[4]
sage.rings.polynomial.polynomial_zmod_flint.make_element()

Previous topic

Dense univariate polynomials over \ZZ, implemented using NTL.

Next topic

Dense univariate polynomials over \ZZ/n\ZZ, implemented using NTL.

This Page