Finite Extension Fields implemented via PARI.

AUTHORS:

  • William Stein: initial version
  • Jeroen Demeyer (2010-12-16): fix formatting of docstrings (trac ticket #10487)
class sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari(q, name, modulus=None)

Bases: sage.rings.finite_rings.finite_field_base.FiniteField

Finite Field of order \(q\), where \(q\) is a prime power (not a prime), implemented using PARI POLMOD. This implementation is the default implementation for \(q \geq 2^{16}\).

INPUT:

  • q – integer, size of the finite field, not prime
  • name – variable used for printing element of the finite field. Also, two finite fields are considered equal if they have the same variable name, and not otherwise.
  • modulus – you may provide a polynomial to use for reduction or a string:
    • 'conway' – force the use of a Conway polynomial, will raise a RuntimeError if none is found in the database
    • 'random' – use a random irreducible polynomial
    • 'default' – a Conway polynomial is used if found. Otherwise a random polynomial is used

OUTPUT:

A finite field of order \(q\) with the given variable name

EXAMPLES:

sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(9, 'a')
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]

Fields can be coerced into sets or list and iterated over:

sage: list(k)
[0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2]

The following is a native Python set:

sage: set(k)
set([0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2])

And the following is a Sage set:

sage: Set(k)
{0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2}

We can also make a list via comprehension:
sage: [x for x in k]
[0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2]

Next we compute with the finite field of order 16, where the name is named b:

sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k16 = FiniteField_ext_pari(16, "b")
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

Of course one can also make prime finite fields:

sage: k = FiniteField(7)

Note that the generator is 1:

sage: k.gen()
1
sage: k.gen().multiplicative_order()
1

Prime finite fields are implemented elsewhere, they cannot be constructed using FiniteField_ext_pari:

sage: k = FiniteField_ext_pari(7, 'a')
Traceback (most recent call last):
...
ValueError: The size of the finite field must not be prime.

Illustration of dumping and loading:

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

In this example \(K\) is large enough that Conway polynomials are not used. Note that when the field is dumped the defining polynomial \(f\) is also dumped. Since \(f\) is determined by a random algorithm, it’s important that \(f\) is dumped as part of \(K\). If you quit Sage and restart and remake a finite field of the same order (and the order is large enough so that there is no Conway polynomial), then defining polynomial is probably different. However, if you load a previously saved field, that will have the same defining polynomial.

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

Note

We do NOT yet define natural consistent inclusion maps between different finite fields.

characteristic()

Returns the characteristic of the finite field, which is a prime number.

EXAMPLES:

sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(3^4, 'a')
sage: k.characteristic()
3
degree()

Returns the degree of the finite field, which is a positive integer.

EXAMPLES:

sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: FiniteField_ext_pari(3^20, 'a').degree()
20
gen(n=0)

Return a generator of the finite field.

This generator is a root of the defining polynomial of the finite field, and might differ between different runs or different architectures.

Warning

This generator is not guaranteed to be a generator for the multiplicative group. To obtain the latter, use multiplicative_generator().

INPUT:

  • n – ignored

OUTPUT:

Field generator of finite field

EXAMPLES:

sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: FiniteField_ext_pari(2^4, "b").gen()
b
sage: k = FiniteField_ext_pari(3^4, "alpha")
sage: a = k.gen()
sage: a
alpha
sage: a^4
alpha^3 + 1
modulus()

Return the minimal polynomial of the generator of self in self.polynomial_ring('x').

EXAMPLES:

sage: F.<a> = GF(7^20, 'a', impl='pari_mod')
sage: f = F.modulus(); f
x^20 + x^12 + 6*x^11 + 2*x^10 + 5*x^9 + 2*x^8 + 3*x^7 + x^6 + 3*x^5 + 3*x^3 + x + 3

sage: f(a)
0
order()

The number of elements of the finite field.

EXAMPLES:

sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(2^10,'a')
sage: k
Finite Field in a of size 2^10
sage: k.order()
1024
polynomial(name=None)

Return the irreducible characteristic polynomial of the generator of this finite field, i.e., the polynomial \(f(x)\) so elements of the finite field as elements modulo \(f\).

EXAMPLES:

sage: k = FiniteField(17)
sage: k.polynomial('x')
x
sage: from sage.rings.finite_rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(9,'a')
sage: k.polynomial('x')
x^2 + 2*x + 2

Previous topic

Base Classes for Finite Fields

Next topic

Givaro Finite Field

This Page