AUTHOR: - Martin Albrecht (2008-10) initial implementation
Univariate Polynomials over GF(2) via NTL’s GF2X.
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x^3 + x^2 + 1
x^3 + x^2 + 1
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: f = x^3 + x^2 + 1; f
x^3 + x^2 + 1
sage: f[0]
1
sage: f[1]
0
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: f = x^3 + x^2 + 1
sage: pari(f)
Mod(1, 2)*x^3 + Mod(1, 2)*x^2 + Mod(1, 2)
Return True precisely if this polynomial is irreducible over GF(2).
EXAMPLES:
sage: R.<x> = GF(2)[]
sage: (x^2 + 1).is_irreducible()
False
sage: (x^3 + x + 1).is_irreducible()
True
Compute .
Both implementations use Brent-Kung’s Algorithm 2.1 (Fast Algorithms for Manipulation of Formal Power Series, JACM 1978).
INPUT:
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: r = 279
sage: f = x^r + x +1
sage: g = x^r
sage: g.modular_composition(g, f) == g(g) % f
True
sage: P.<x> = GF(2)[]
sage: f = x^29 + x^24 + x^22 + x^21 + x^20 + x^16 + x^15 + x^14 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^2
sage: g = x^31 + x^30 + x^28 + x^26 + x^24 + x^21 + x^19 + x^18 + x^11 + x^10 + x^9 + x^8 + x^5 + x^2 + 1
sage: h = x^30 + x^28 + x^26 + x^25 + x^24 + x^22 + x^21 + x^18 + x^17 + x^15 + x^13 + x^12 + x^11 + x^10 + x^9 + x^4
sage: f.modular_composition(g,h) == f(g) % h
True
AUTHORS:
Template for interfacing to external C / C++ libraries for implementations of polynomials.
AUTHORS:
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
.
Note
Implementations using this template MUST implement coercion from base ring elements and __getitem__. See Polynomial_GF2X for an example.
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: copy(x) is x
False
sage: copy(x) == x
True
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x//(x + 1)
1
sage: (x + 1)//x
1
x.__getslice__(i, j) <==> x[i:j]
Use of negative indices is not supported.
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: int(x)
...
ValueError: Cannot coerce polynomial with degree 1 to integer.
sage: int(P(1))
1
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: f = x^3 + x^2 + 1
sage: f << 1
x^4 + x^3 + x
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: (x^2 + 1) % x^2
1
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: -x
x
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: loads(dumps(x)) == x
True
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
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x + 1
x + 1
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
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x*(x+1)
x^2 + x
Return Singular representation of this polynomial
INPUT:
EXAMPLE:
sage: P.<x> = PolynomialRing(GF(7))
sage: f = 3*x^2 + 2*x + 5
sage: singular(f)
3*x^2+2*x-2
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x - 1
x + 1
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x.degree()
1
sage: P(1).degree()
0
sage: P(0).degree()
-1
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
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x.is_gen()
True
sage: (x+1).is_gen()
False
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: P(1).is_one()
True
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x.is_zero()
False
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: x.list()
[0, 1]
sage: list(x)
[0, 1]
EXAMPLE:
sage: P.<x> = GF(2)[]
sage: f = x^2 + x + 1
sage: f.quo_rem(x + 1)
(x, 1)
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
Returns this polynomial mod .
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
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)