Finite fields implemented via PARI’s FFELT type

AUTHORS:

• Peter Bruin (June 2013): initial version, based on finite_field_ext_pari.py by William Stein et al.

class sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt(p, modulus, name=None)

Bases: FiniteField

Finite fields whose cardinality is a prime power (not a prime), implemented using PARI’s FFELT type.

INPUT:

• p – prime number

• modulus – an irreducible polynomial of degree at least 2 over the field of \(p\) elements

• name – string: name of the distinguished generator (default: variable name of modulus)

OUTPUT:

A finite field of order \(q = p^n\), generated by a distinguished element with minimal polynomial modulus. Elements are represented as polynomials in name of degree less than \(n\).

Note

Direct construction of FiniteField_pari_ffelt objects requires specifying a characteristic and a modulus. To construct a finite field by specifying a cardinality and an algorithm for finding an irreducible polynomial, use the FiniteField constructor with impl='pari_ffelt'.

EXAMPLES:

Some computations with a finite field of order 9:

Sage

sage: k = FiniteField(9, 'a', impl='pari_ffelt')
sage: k
Finite Field in a of size 3^2
sage: k.is_field()
True
sage: k.characteristic()
3
sage: a = k.gen()
sage: a
a
sage: a.parent()
Finite Field in a of size 3^2
sage: a.charpoly('x')
x^2 + 2*x + 2
sage: [a^i for i in range(8)]
[1, a, a + 1, 2*a + 1, 2, 2*a, 2*a + 2, a + 2]
sage: TestSuite(k).run()

Python

>>> from sage.all import *
>>> k = FiniteField(Integer(9), 'a', impl='pari_ffelt')
>>> k
Finite Field in a of size 3^2
>>> k.is_field()
True
>>> k.characteristic()
3
>>> a = k.gen()
>>> a
a
>>> a.parent()
Finite Field in a of size 3^2
>>> a.charpoly('x')
x^2 + 2*x + 2
>>> [a**i for i in range(Integer(8))]
[1, a, a + 1, 2*a + 1, 2, 2*a, 2*a + 2, a + 2]
>>> TestSuite(k).run()

Next we compute with a finite field of order 16:

Sage

sage: k16 = FiniteField(16, 'b', impl='pari_ffelt')
sage: z = k16.gen()
sage: z
b
sage: z.charpoly('x')
x^4 + x + 1
sage: k16.is_field()
True
sage: k16.characteristic()
2
sage: z.multiplicative_order()
15

Python

>>> from sage.all import *
>>> k16 = FiniteField(Integer(16), 'b', impl='pari_ffelt')
>>> z = k16.gen()
>>> z
b
>>> z.charpoly('x')
x^4 + x + 1
>>> k16.is_field()
True
>>> k16.characteristic()
2
>>> z.multiplicative_order()
15

Illustration of dumping and loading:

Sage

sage: K = FiniteField(7^10, 'b', impl='pari_ffelt')
sage: loads(K.dumps()) == K
True

sage: K = FiniteField(10007^10, 'a', impl='pari_ffelt')
sage: loads(K.dumps()) == K
True

Python

>>> from sage.all import *
>>> K = FiniteField(Integer(7)**Integer(10), 'b', impl='pari_ffelt')
>>> loads(K.dumps()) == K
True

>>> K = FiniteField(Integer(10007)**Integer(10), 'a', impl='pari_ffelt')
>>> loads(K.dumps()) == K
True

Element

alias of FiniteFieldElement_pari_ffelt

characteristic()

Return the characteristic of self.

EXAMPLES:

Sage

sage: F = FiniteField(3^4, 'a', impl='pari_ffelt')
sage: F.characteristic()
3

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(3)**Integer(4), 'a', impl='pari_ffelt')
>>> F.characteristic()
3

degree()

Returns the degree of self over its prime field.

EXAMPLES:

Sage

sage: F = FiniteField(3^20, 'a', impl='pari_ffelt')
sage: F.degree()
20

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(3)**Integer(20), 'a', impl='pari_ffelt')
>>> F.degree()
20

gen(n=0)

Return a generator of self over its prime field, which is a root of self.modulus().

INPUT:

• n – must be 0

OUTPUT:

An element \(a\) of self such that self.modulus()(a) == 0.

Warning

This generator is not guaranteed to be a generator for the multiplicative group. To obtain the latter, use multiplicative_generator() or use the modulus="primitive" option when constructing the field.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(GF(2))
sage: FiniteField(2^4, 'b', impl='pari_ffelt').gen()
b
sage: k = FiniteField(3^4, 'alpha', impl='pari_ffelt')
sage: a = k.gen()
sage: a
alpha
sage: a^4
alpha^3 + 1

Python

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(2)), names=('x',)); (x,) = R._first_ngens(1)
>>> FiniteField(Integer(2)**Integer(4), 'b', impl='pari_ffelt').gen()
b
>>> k = FiniteField(Integer(3)**Integer(4), 'alpha', impl='pari_ffelt')
>>> a = k.gen()
>>> a
alpha
>>> a**Integer(4)
alpha^3 + 1