Elements of finite fields of characteristic 2#

This implementation uses NTL’s GF2E class to perform the arithmetic and is the standard implementation for GF(2^n) for n >= 16.

AUTHORS:

class sage.rings.finite_rings.element_ntl_gf2e.Cache_ntl_gf2e[source]#

Bases: Cache_base

This class stores information for an NTL finite field in a Cython class so that elements can access it quickly.

It’s modeled on NativeIntStruct, but includes many functions that were previously included in the parent (see Issue #12062).

degree()[source]#

If the field has cardinality \(2^n\) this method returns \(n\).

EXAMPLES:

sage: k.<a> = GF(2^64)
sage: k._cache.degree()
64

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(64), names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.degree()
64
fetch_int(number)[source]#

Given an integer less than \(p^n\) with base \(2\) representation \(a_0 + a_1 \cdot 2 + \cdots + a_k 2^k\), this returns \(a_0 + a_1 x + \cdots + a_k x^k\), where \(x\) is the generator of this finite field.

INPUT:

  • number – an integer, of size less than the cardinality

EXAMPLES:

sage: k.<a> = GF(2^48)
sage: k._cache.fetch_int(2^33 + 2 + 1)
a^33 + a + 1

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(48), names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.fetch_int(Integer(2)**Integer(33) + Integer(2) + Integer(1))
a^33 + a + 1
import_data(e)[source]#

EXAMPLES:

sage: k.<a> = GF(2^17)
sage: V = k.vector_space(map=False)
sage: v = [1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0]
sage: k._cache.import_data(v)
a^13 + a^8 + a^5 + 1
sage: k._cache.import_data(V(v))
a^13 + a^8 + a^5 + 1

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(17), names=('a',)); (a,) = k._first_ngens(1)
>>> V = k.vector_space(map=False)
>>> v = [Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)]
>>> k._cache.import_data(v)
a^13 + a^8 + a^5 + 1
>>> k._cache.import_data(V(v))
a^13 + a^8 + a^5 + 1
order()[source]#

Return the cardinality of the field.

EXAMPLES:

sage: k.<a> = GF(2^64)
sage: k._cache.order()
18446744073709551616

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(64), names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.order()
18446744073709551616
polynomial()[source]#

Returns the list of 0’s and 1’s giving the defining polynomial of the field.

EXAMPLES:

sage: k.<a> = GF(2^20,modulus="minimal_weight")
sage: k._cache.polynomial()
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(20),modulus="minimal_weight", names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.polynomial()
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
class sage.rings.finite_rings.element_ntl_gf2e.FiniteField_ntl_gf2eElement[source]#

Bases: FinitePolyExtElement

An element of an NTL:GF2E finite field.

charpoly(var='x')[source]#

Return the characteristic polynomial of self as a polynomial in var over the prime subfield.

INPUT:

  • var – string (default: 'x')

OUTPUT:

polynomial

EXAMPLES:

sage: k.<a> = GF(2^8, impl="ntl")
sage: b = a^3 + a
sage: b.minpoly()
x^4 + x^3 + x^2 + x + 1
sage: b.charpoly()
x^8 + x^6 + x^4 + x^2 + 1
sage: b.charpoly().factor()
(x^4 + x^3 + x^2 + x + 1)^2
sage: b.charpoly('Z')
Z^8 + Z^6 + Z^4 + Z^2 + 1

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), impl="ntl", names=('a',)); (a,) = k._first_ngens(1)
>>> b = a**Integer(3) + a
>>> b.minpoly()
x^4 + x^3 + x^2 + x + 1
>>> b.charpoly()
x^8 + x^6 + x^4 + x^2 + 1
>>> b.charpoly().factor()
(x^4 + x^3 + x^2 + x + 1)^2
>>> b.charpoly('Z')
Z^8 + Z^6 + Z^4 + Z^2 + 1
is_one()[source]#

Return True if self == k(1).

Equivalent to self != k(0).

EXAMPLES:

sage: k.<a> = GF(2^20)
sage: a.is_one() # indirect doctest
False
sage: k(1).is_one()
True

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(20), names=('a',)); (a,) = k._first_ngens(1)
>>> a.is_one() # indirect doctest
False
>>> k(Integer(1)).is_one()
True
is_square()[source]#

Return True as every element in \(\GF{2^n}\) is a square.

EXAMPLES:

sage: k.<a> = GF(2^18)
sage: e = k.random_element()
sage: e.parent() is k
True
sage: e.is_square()
True
sage: e.sqrt()^2 == e
True

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(18), names=('a',)); (a,) = k._first_ngens(1)
>>> e = k.random_element()
>>> e.parent() is k
True
>>> e.is_square()
True
>>> e.sqrt()**Integer(2) == e
True
is_unit()[source]#

Return True if self is nonzero, so it is a unit as an element of the finite field.

EXAMPLES:

sage: k.<a> = GF(2^17)
sage: a.is_unit()
True
sage: k(0).is_unit()
False

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(17), names=('a',)); (a,) = k._first_ngens(1)
>>> a.is_unit()
True
>>> k(Integer(0)).is_unit()
False
log(base)[source]#

Compute an integer \(x\) such that \(b^x = a\), where \(a\) is self and \(b\) is base.

INPUT:

  • base – finite field element

OUTPUT:

Integer \(x\) such that \(a^x = b\), if it exists. Raises a ValueError exception if no such \(x\) exists.

ALGORITHM: pari:fflog

EXAMPLES:

sage: F = FiniteField(2^10, 'a')
sage: g = F.gen()
sage: b = g; a = g^37
sage: a.log(b)
37
sage: b^37; a
a^8 + a^7 + a^4 + a + 1
a^8 + a^7 + a^4 + a + 1

>>> from sage.all import *
>>> F = FiniteField(Integer(2)**Integer(10), 'a')
>>> g = F.gen()
>>> b = g; a = g**Integer(37)
>>> a.log(b)
37
>>> b**Integer(37); a
a^8 + a^7 + a^4 + a + 1
a^8 + a^7 + a^4 + a + 1

Big instances used to take a very long time before Issue #32842:

sage: g = GF(2^61).gen()
sage: g.log(g^7)
1976436865040309101

>>> from sage.all import *
>>> g = GF(Integer(2)**Integer(61)).gen()
>>> g.log(g**Integer(7))
1976436865040309101

AUTHORS:

minpoly(var='x')[source]#

Return the minimal polynomial of self, which is the smallest degree polynomial \(f \in \GF{2}[x]\) such that f(self) == 0.

INPUT:

  • var – string (default: 'x')

OUTPUT:

polynomial

EXAMPLES:

sage: K.<a> = GF(2^100)
sage: f = a.minpoly(); f
x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1
sage: f(a)
0
sage: g = K.random_element()
sage: g.minpoly()(g)
0

>>> from sage.all import *
>>> K = GF(Integer(2)**Integer(100), names=('a',)); (a,) = K._first_ngens(1)
>>> f = a.minpoly(); f
x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1
>>> f(a)
0
>>> g = K.random_element()
>>> g.minpoly()(g)
0
polynomial(name=None)[source]#

Return self viewed as a polynomial over self.parent().prime_subfield().

INPUT:

  • name – (optional) variable name

EXAMPLES:

sage: k.<a> = GF(2^17)
sage: e = a^15 + a^13 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^4 + a + 1
sage: e.polynomial()
a^15 + a^13 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^4 + a + 1

sage: from sage.rings.polynomial.polynomial_element import Polynomial
sage: isinstance(e.polynomial(), Polynomial)
True

sage: e.polynomial('x')
x^15 + x^13 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^4 + x + 1

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(17), names=('a',)); (a,) = k._first_ngens(1)
>>> e = a**Integer(15) + a**Integer(13) + a**Integer(11) + a**Integer(10) + a**Integer(9) + a**Integer(8) + a**Integer(7) + a**Integer(6) + a**Integer(4) + a + Integer(1)
>>> e.polynomial()
a^15 + a^13 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^4 + a + 1

>>> from sage.rings.polynomial.polynomial_element import Polynomial
>>> isinstance(e.polynomial(), Polynomial)
True

>>> e.polynomial('x')
x^15 + x^13 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^4 + x + 1
sqrt(all=False, extend=False)[source]#

Return a square root of this finite field element in its parent.

EXAMPLES:

sage: k.<a> = GF(2^20)
sage: a.is_square()
True
sage: a.sqrt()
a^19 + a^15 + a^14 + a^12 + a^9 + a^7 + a^4 + a^3 + a + 1
sage: a.sqrt()^2 == a
True

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(20), names=('a',)); (a,) = k._first_ngens(1)
>>> a.is_square()
True
>>> a.sqrt()
a^19 + a^15 + a^14 + a^12 + a^9 + a^7 + a^4 + a^3 + a + 1
>>> a.sqrt()**Integer(2) == a
True

This failed before Issue #4899:

sage: GF(2^16,'a')(1).sqrt()
1

>>> from sage.all import *
>>> GF(Integer(2)**Integer(16),'a')(Integer(1)).sqrt()
1
trace()[source]#

Return the trace of self.

EXAMPLES:

sage: K.<a> = GF(2^25)
sage: a.trace()
0
sage: a.charpoly()
x^25 + x^8 + x^6 + x^2 + 1
sage: parent(a.trace())
Finite Field of size 2

sage: b = a+1
sage: b.trace()
1
sage: b.charpoly()[1]
1

>>> from sage.all import *
>>> K = GF(Integer(2)**Integer(25), names=('a',)); (a,) = K._first_ngens(1)
>>> a.trace()
0
>>> a.charpoly()
x^25 + x^8 + x^6 + x^2 + 1
>>> parent(a.trace())
Finite Field of size 2

>>> b = a+Integer(1)
>>> b.trace()
1
>>> b.charpoly()[Integer(1)]
1
weight()[source]#

Returns the number of non-zero coefficients in the polynomial representation of self.

EXAMPLES:

sage: K.<a> = GF(2^21)
sage: a.weight()
1
sage: (a^5+a^2+1).weight()
3
sage: b = 1/(a+1); b
a^20 + a^19 + a^18 + a^17 + a^16 + a^15 + a^14 + a^13 + a^12 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^4 + a^3 + a^2
sage: b.weight()
18

>>> from sage.all import *
>>> K = GF(Integer(2)**Integer(21), names=('a',)); (a,) = K._first_ngens(1)
>>> a.weight()
1
>>> (a**Integer(5)+a**Integer(2)+Integer(1)).weight()
3
>>> b = Integer(1)/(a+Integer(1)); b
a^20 + a^19 + a^18 + a^17 + a^16 + a^15 + a^14 + a^13 + a^12 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^4 + a^3 + a^2
>>> b.weight()
18
sage.rings.finite_rings.element_ntl_gf2e.unpickleFiniteField_ntl_gf2eElement(parent, elem)[source]#

EXAMPLES:

sage: k.<a> = GF(2^20)
sage: e = k.random_element()
sage: f = loads(dumps(e)) # indirect doctest
sage: e == f
True

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(20), names=('a',)); (a,) = k._first_ngens(1)
>>> e = k.random_element()
>>> f = loads(dumps(e)) # indirect doctest
>>> e == f
True