Univariate Polynomials over GF(2) via NTL’s GF2X

AUTHOR: - Martin Albrecht (2008-10) initial implementation

sage.rings.polynomial.polynomial_gf2x.GF2X_BuildIrred_list(n)

Return the list of coefficients of the lexicographically smallest irreducible polynomial of degree \(n\) over the field of 2 elements.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildIrred_list
sage: GF2X_BuildIrred_list(2)
[1, 1, 1]
sage: GF2X_BuildIrred_list(3)
[1, 1, 0, 1]
sage: GF2X_BuildIrred_list(4)
[1, 1, 0, 0, 1]
sage: GF(2)['x'](GF2X_BuildIrred_list(33))
x^33 + x^6 + x^3 + x + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildIrred_list
>>> GF2X_BuildIrred_list(Integer(2))
[1, 1, 1]
>>> GF2X_BuildIrred_list(Integer(3))
[1, 1, 0, 1]
>>> GF2X_BuildIrred_list(Integer(4))
[1, 1, 0, 0, 1]
>>> GF(Integer(2))['x'](GF2X_BuildIrred_list(Integer(33)))
x^33 + x^6 + x^3 + x + 1

sage.rings.polynomial.polynomial_gf2x.GF2X_BuildRandomIrred_list(n)

Return the list of coefficients of an irreducible polynomial of degree \(n\) of minimal weight over the field of 2 elements.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildRandomIrred_list
sage: GF2X_BuildRandomIrred_list(2)
[1, 1, 1]
sage: GF2X_BuildRandomIrred_list(3) in [[1, 1, 0, 1], [1, 0, 1, 1]]
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildRandomIrred_list
>>> GF2X_BuildRandomIrred_list(Integer(2))
[1, 1, 1]
>>> GF2X_BuildRandomIrred_list(Integer(3)) in [[Integer(1), Integer(1), Integer(0), Integer(1)], [Integer(1), Integer(0), Integer(1), Integer(1)]]
True

sage.rings.polynomial.polynomial_gf2x.GF2X_BuildSparseIrred_list(n)

Return the list of coefficients of an irreducible polynomial of degree \(n\) of minimal weight over the field of 2 elements.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildIrred_list, GF2X_BuildSparseIrred_list
sage: all([GF2X_BuildSparseIrred_list(n) == GF2X_BuildIrred_list(n)
....:      for n in range(1,33)])
True
sage: GF(2)['x'](GF2X_BuildSparseIrred_list(33))
x^33 + x^10 + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildIrred_list, GF2X_BuildSparseIrred_list
>>> all([GF2X_BuildSparseIrred_list(n) == GF2X_BuildIrred_list(n)
...      for n in range(Integer(1),Integer(33))])
True
>>> GF(Integer(2))['x'](GF2X_BuildSparseIrred_list(Integer(33)))
x^33 + x^10 + 1

class sage.rings.polynomial.polynomial_gf2x.Polynomial_GF2X

Bases: Polynomial_template

Univariate Polynomials over \(\GF{2}\) via NTL’s GF2X.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x**Integer(3) + x**Integer(2) + Integer(1)
x^3 + x^2 + 1

compose_mod(g, h, algorithm=None)

Compute \(f(g) \pmod h\).

Both implementations use Brent-Kung’s Algorithm 2.1 (Fast Algorithms for Manipulation of Formal Power Series, JACM 1978).

INPUT:

• g – a polynomial

• h – a polynomial

• algorithm – either 'native' or 'ntl' (default: 'native')

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> r = Integer(279)
>>> f = x**r + x +Integer(1)
>>> g = x**r
>>> g.modular_composition(g, f) == g(g) % f
True

>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(29) + x**Integer(24) + x**Integer(22) + x**Integer(21) + x**Integer(20) + x**Integer(16) + x**Integer(15) + x**Integer(14) + x**Integer(10) + x**Integer(9) + x**Integer(8) + x**Integer(7) + x**Integer(6) + x**Integer(5) + x**Integer(2)
>>> g = x**Integer(31) + x**Integer(30) + x**Integer(28) + x**Integer(26) + x**Integer(24) + x**Integer(21) + x**Integer(19) + x**Integer(18) + x**Integer(11) + x**Integer(10) + x**Integer(9) + x**Integer(8) + x**Integer(5) + x**Integer(2) + Integer(1)
>>> h = x**Integer(30) + x**Integer(28) + x**Integer(26) + x**Integer(25) + x**Integer(24) + x**Integer(22) + x**Integer(21) + x**Integer(18) + x**Integer(17) + x**Integer(15) + x**Integer(13) + x**Integer(12) + x**Integer(11) + x**Integer(10) + x**Integer(9) + x**Integer(4)
>>> f.modular_composition(g, h) == f(g) % h
True

AUTHORS:

• Paul Zimmermann (2008-10) initial implementation

• Martin Albrecht (2008-10) performance improvements

is_irreducible()

Return whether this polynomial is irreducible over \(\GF{2}\).

EXAMPLES:

Sage

sage: R.<x> = GF(2)[]
sage: (x^2 + 1).is_irreducible()
False
sage: (x^3 + x + 1).is_irreducible()
True

Python

>>> from sage.all import *
>>> R = GF(Integer(2))['x']; (x,) = R._first_ngens(1)
>>> (x**Integer(2) + Integer(1)).is_irreducible()
False
>>> (x**Integer(3) + x + Integer(1)).is_irreducible()
True

Test that caching works:

Sage

sage: R.<x> = GF(2)[]
sage: f = x^2 + 1
sage: f.is_irreducible()
False
sage: f.is_irreducible.cache
False

Python

>>> from sage.all import *
>>> R = GF(Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + Integer(1)
>>> f.is_irreducible()
False
>>> f.is_irreducible.cache
False

modular_composition(g, h, algorithm=None)

Compute \(f(g) \pmod h\).

Both implementations use Brent-Kung’s Algorithm 2.1 (Fast Algorithms for Manipulation of Formal Power Series, JACM 1978).

INPUT:

• g – a polynomial

• h – a polynomial

• algorithm – either 'native' or 'ntl' (default: 'native')

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> r = Integer(279)
>>> f = x**r + x +Integer(1)
>>> g = x**r
>>> g.modular_composition(g, f) == g(g) % f
True

>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(29) + x**Integer(24) + x**Integer(22) + x**Integer(21) + x**Integer(20) + x**Integer(16) + x**Integer(15) + x**Integer(14) + x**Integer(10) + x**Integer(9) + x**Integer(8) + x**Integer(7) + x**Integer(6) + x**Integer(5) + x**Integer(2)
>>> g = x**Integer(31) + x**Integer(30) + x**Integer(28) + x**Integer(26) + x**Integer(24) + x**Integer(21) + x**Integer(19) + x**Integer(18) + x**Integer(11) + x**Integer(10) + x**Integer(9) + x**Integer(8) + x**Integer(5) + x**Integer(2) + Integer(1)
>>> h = x**Integer(30) + x**Integer(28) + x**Integer(26) + x**Integer(25) + x**Integer(24) + x**Integer(22) + x**Integer(21) + x**Integer(18) + x**Integer(17) + x**Integer(15) + x**Integer(13) + x**Integer(12) + x**Integer(11) + x**Integer(10) + x**Integer(9) + x**Integer(4)
>>> f.modular_composition(g, h) == f(g) % h
True

AUTHORS:

• Paul Zimmermann (2008-10) initial implementation

• Martin Albrecht (2008-10) performance improvements

class sage.rings.polynomial.polynomial_gf2x.Polynomial_template

Bases: Polynomial

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 get_unsafe(). See Polynomial_GF2X for an example.

degree()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.degree()
1
>>> P(Integer(1)).degree()
0
>>> P(Integer(0)).degree()
-1

gcd(other)

Return the greatest common divisor of self and other.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x*(x+Integer(1))
>>> f.gcd(x+Integer(1))
x + 1
>>> f.gcd(x**Integer(2))
x

get_cparent()

is_gen()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.is_gen()
True
>>> (x+Integer(1)).is_gen()
False

is_one()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> P(Integer(1)).is_one()
True

is_zero()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.is_zero()
False

list(copy=True)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.list()
[0, 1]
>>> list(x)
[0, 1]

quo_rem(right)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(2) + x + Integer(1)
>>> f.quo_rem(x + Integer(1))
(x, 1)

shift(n)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(3) + x**Integer(2) + Integer(1)
>>> f.shift(Integer(1))
x^4 + x^3 + x
>>> f.shift(-Integer(1))
x^2 + x

truncate(n)

Return this polynomial mod \(x^n\).

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = GF(Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = sum(x**n for n in range(Integer(10))); f
x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
>>> f.truncate(Integer(6))
x^5 + x^4 + x^3 + x^2 + x + 1

If the precision is higher than the degree of the polynomial then the polynomial itself is returned:

Sage

sage: f.truncate(10) is f
True

Python

>>> from sage.all import *
>>> f.truncate(Integer(10)) is f
True

If the precision is negative, the zero polynomial is returned:

Sage

sage: f.truncate(-1)
0

Python

>>> from sage.all import *
>>> f.truncate(-Integer(1))
0

xgcd(other)

Compute extended gcd of self and other.

EXAMPLES:

Sage

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)

Python

>>> from sage.all import *
>>> P = GF(Integer(7))['x']; (x,) = P._first_ngens(1)
>>> f = x*(x+Integer(1))
>>> f.xgcd(x+Integer(1))
(x + 1, 0, 1)
>>> f.xgcd(x**Integer(2))
(x, 1, 6)

sage.rings.polynomial.polynomial_gf2x.make_element(parent, args)