12.7 Finite Fields

Module: sage.rings.finite_field

Finite Fields support iteration, starting with 0.

sage: k = GF(9, 'a')
sage: i = 0
sage: for x in k: print i, x; i+=1
0 0
1 1
2 2
3 a
4 a + 1
5 a + 2
6 2*a
7 2*a + 1
8 2*a + 2

Module-level Functions

FiniteField( order, [name=a])

Return a finite field of given order with generator labeled by the given name.

INPUT:
    order -- int
    name -- string (default: 'a')

sage: k, a = GF(9).objgen()
sage: k
Finite Field in a of size 3^2
sage: k.assign_names(['b'])
sage: k
Finite Field in b of size 3^2
sage: GF(9,'a')
Finite Field in a of size 3^2

GF( order, [name=a])

Synonym for FiniteField.

conway_polynomial( p, n)

Return the Conway polynomial of degree n over GF(p), which is loaded from a table.

If the requested polynomial is not known, this function raises a RuntimeError exception.

INPUT:
    p -- int
    n -- int
    
OUTPUT:
    Polynomial -- a polynomial over the prime finite field GF(p).

NOTE: The first time this function is called a table is read from disk, which takes a fraction of a second. Subsequent calls do not require reloading the table.

See also the ConwayPolynomials() object, which is a table of Conway polynomials. For example, if c=ConwayPolynomials, then c.primes() is a list of all primes for which the polynomials are known, and for a given prime p, c.degree(p) is a list of all degrees for which the Conway polynomials are known.

sage: conway_polynomial(2,5)
x^5 + x^2 + 1
sage: conway_polynomial(101,5)
x^5 + 2*x + 99
sage: conway_polynomial(97,101)
Traceback (most recent call last):
...
RuntimeError: Conway polynomial over F_97 of degree 101 not in database.

exists_conway_polynomial( p, n)

Return True if the Conway polynomial over F_p of degree n is in the database and False otherwise.

If the Conway polynomial is in the database, to obtain it use the command conway_polynomial(p,n).

sage: exists_conway_polynomial(2,3)
True
sage: exists_conway_polynomial(2,-1)
False
sage: exists_conway_polynomial(97,200)
False
sage: exists_conway_polynomial(6,6)
False

gap_to_sage( x, F)

INPUT:
    x -- gap finite field element
    F -- SAGE finite field
OUTPUT:
    element of F

sage: x = gap('Z(13)')
sage: F = GF(13)
sage: F(x)
2
sage: F(gap('0*Z(13)'))
0
sage: F = GF(13^2)
sage: x = gap('Z(13)')
sage: F(x)
2
sage: x = gap('Z(13^2)^3')
sage: F(x)
12*a + 11
sage: F.multiplicative_generator()^3
12*a + 11

Author: David Joyner and William Stein

is_FiniteField( x)

is_PrimeFiniteField( x)

Class: FiniteField_ext_pari

class FiniteField_ext_pari
Finite Field of order q, where q is a nontrivial prime power. (Implemented using PARI mod's.)

Create with the command FiniteField(order)

INPUT: q - int, prime power, order of the finite field name - string (default: 'a'), string for printing the generator

OUTPUT: FiniteField - finite field of order q.

sage: k = FiniteField(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^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([a, 2*a + 1, a + 2, a + 1, 2*a + 2, 1, 0, 2, 2*a])

And the following is a SAGE enumerated set:

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

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: k16 = FiniteField(16, "b")
sage: z = k16.gen()
sage: z
b
sage: z.charpoly()
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

Illustration of dumping and loading:

sage: K = GF(7)
sage: loads(K.dumps()) == K
True
sage: K = GF(7^10)
sage: loads(K.dumps()) == K
True
sage: K = GF(7^10, 'a')
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)
sage: loads(K.dumps()) == K
True
FiniteField_ext_pari( self, q, [name=None], [modulus=a])

Create finite field of order q with variable printed as name.

INPUT:
    q -- integer, size of the finite field, not prime
    name -- (optional:default 'a') 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.
OUTPUT:
    FiniteField -- a finite field of order q with given variable name.

sage: FiniteField(17)
Finite Field of size 17
sage: FiniteField(2^10)
Finite Field in a of size 2^10
sage: FiniteField(3^5, "b")
Finite Field in b of size 3^5
sage: FiniteField(3^5, "b").gen()
b

You can also create a finite field using GF, which is a synonym for FiniteField.

sage: GF(19**2)
Finite Field in a of size 19^2

Functions: characteristic,$  $ degree,$  $ gen,$  $ is_prime,$  $ is_prime_field,$  $ modulus,$  $ order,$  $ polynomial

characteristic( self)

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

sage: k = FiniteField(3**4)
sage: k.characteristic()
3

degree( self)

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

sage: FiniteField(3).degree()
1
sage: FiniteField(3**20).degree()
20

gen( self, [n=0])

Return chosen generator of the finite field. This generator is a root of the defining polynomial of the finite field, and is guaranteed to be a generator for the multiplicative group.

INPUT:
    nothing

OUTPUT:
    FiniteFieldElement -- field generator of finite field

sage: FiniteField(2**4, "b").gen()
b
sage: k = FiniteField(3**4, "alpha")
sage: a = k.gen()
sage: a
alpha
sage: a**4
alpha^3 + 1

order( self)

The number of elements of the finite field.

sage: k = GF(2**10)
sage: k
Finite Field in a of size 2^10
sage: k.order()
1024

polynomial( self)

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.

sage: k = FiniteField(17)
sage: k.polynomial()
x
sage: k = FiniteField(9)
sage: k.polynomial()
x^2 + 2*x + 2

Special Functions: __call__,$  $ __cmp__,$  $ __len__,$  $ __repr__,$  $ _coerce_,$  $ _pari_modulus,$  $ _pari_one

__call__( self, x)

Coerce x into the finite field.

INPUT:
    x -- object

OUTPUT:
    FiniteFieldElement -- if possible, makes a finite field element from x.

sage: k = GF(3^4)
sage: b = k(5)
sage: b.parent()
Finite Field in a of size 3^4
sage: a = k.gen()
sage: k(a + 2)
a + 2

Constant polynomials coerce into finite fields:

sage: R = QQ['x']
sage: k, a = GF(5^2).objgen()
sage: k(R(2/3))
4
sage: R, x = k['x'].objgen()
sage: k(R(3))
3

Nonconstant polynomials do not coerce:

sage: k(x)
Traceback (most recent call last):
...
TypeError: no coercion of non-constant polynomial x into Finite Field in a
of size 5^2 defined.
sage: k(R(a))
a

Multivariate polynomials also coerce:

sage: R = k['x,y,z']; R
Polynomial Ring in x, y, z over Finite Field in a of size 5^2
sage: k(R(2))
2
sage: R = QQ['x,y,z']
sage: k(R(1/5))
Traceback (most recent call last):
...
TypeError: Unable to coerce 1/5 into Finite Field in a of size 5^2.

Note: Finite Fields are currently implemented using polynomials modulo p and the PARI ffinit function. In particular, we do not use Conway polynomials and do not yet define natural consistent inclusion maps between different finite fields.

Gap elements can also be coerced into finite fields.

sage: F = GF(8, 'a')
sage: a = F.multiplicative_generator(); a
a
sage: b = gap(a^3); b
Z(2^3)^3
sage: F(b)
a + 1
sage: a^3
a + 1

sage: a = GF(13)(gap('0*Z(13)')); a
0
sage: a.parent()
Finite Field of size 13

sage: F = GF(16)
sage: F(gap('Z(16)^3'))
a^3
sage: F(gap('Z(16)^2'))
a^2

You can also call a finite extension field with a string to produce an element of that field, like this:

sage: k = GF(2^8, 'a')
sage: k('a^200')
a^4 + a^3 + a^2

This is especially useful for fast conversions from Singular etc. to FiniteFieldElements.

Author Log:

__cmp__( self, other)

sage: GF(7)(2) == GF(7)(9)
True
sage: GF(7)(2) == GF(11)(2)
False
sage: GF(7)(2) == GF(8)(2)
False
sage: GF(7)(2) == 2
True

__len__( self)

The number of elements of the finite field.

sage: k = GF(2**10)
sage: k
Finite Field in a of size 2^10
sage: len(k)
1024

_coerce_( self, x)

Canonical coercion to self.

sage: GF(4)._coerce_(GF(2)(1))
1
sage: GF(4)._coerce_(GF(4).0)
a
sage: GF(4)._coerce_(3)
1
sage: GF(4)._coerce_(2/3)
Traceback (most recent call last):
...
TypeError: no canonical coercion of 2/3 to Finite Field in a of size 2^2
sage: GF(8)._coerce_(GF(4).0)
Traceback (most recent call last):
...
TypeError: no canonical coercion of a to Finite Field in a of size 2^3
sage: GF(16)._coerce_(GF(4).0)
Traceback (most recent call last):
...
TypeError: no canonical coercion of a to Finite Field in a of size 2^4
defined; adding this is planned (see rings/finite_field.py to help!)
sage: k = GF(8)
sage: k._coerce_(GF(7)(2))
Traceback (most recent call last):
...
TypeError: no canonical coercion of 2 to Finite Field in a of size 2^3

_pari_modulus( self)

The polynomial mod p that defines the finite field, as a PARI object. This is implementation specific, and some finite fields might not be implemented using PARI, so you should avoid using this function.

INPUT:  nothing
OUTPUT:
    gen -- a pari polynomial gen

sage: GF(19**2, 'a')._pari_modulus()
Mod(1, 19)*a^2 + Mod(18, 19)*a + Mod(2, 19)

sage: GF(13**3, 'a')._pari_modulus()
Mod(1, 13)*a^3 + Mod(2, 13)*a + Mod(11, 13)

Note that the PARI modulus is always in terms of a, even if the field variable isn't. This is because the specific choice of variable name has meaning in PARI, i.e., it can't be arbitrary.

sage: FiniteField(2**4, "b")._pari_modulus()
Mod(1, 2)*a^4 + Mod(1, 2)*a + Mod(1, 2)

_pari_one( self)

The PARI object Mod(1,p). This is implementation specific and should be ignored by users.

Class: FiniteField_generic

class FiniteField_generic
FiniteField_generic( self)

sage: K = GF(7); K
Finite Field of size 7
sage: loads(K.dumps()) == K
True
sage: GF(7^10)
Finite Field in a of size 7^10
sage: K = GF(7^10, 'a'); K
Finite Field in a of size 7^10
sage: loads(K.dumps()) == K
True

Functions: cardinality,$  $ gen,$  $ is_field,$  $ is_finite,$  $ multiplicative_generator,$  $ ngens,$  $ order,$  $ polynomial,$  $ polynomial_ring,$  $ random_element,$  $ unit_group_exponent,$  $ vector_space,$  $ zeta,$  $ zeta_order

cardinality( self)

Same as self.order().

is_field( self)

Returns whether or not the finite field is a field, i.e., always returns True.

sage: k = FiniteField(3**4)
sage: k.is_field()
True

multiplicative_generator( self)

Return a generator for the multiplicative group of this field. The generator is not randomized, though it could change from one version of SAGE to another.

sage: k = GF(997)
sage: k.multiplicative_generator()
7
sage: k = GF(11**3, name='a')
sage: k.multiplicative_generator()
a

ngens( self)

The number of generators of the finite field. Always 1.

sage: k = FiniteField(3**4)
sage: k.ngens()
1

polynomial_ring( self)

Returns the polynomial ring over the prime subfield in the same variable as this finite field.

sage: k = FiniteField(3**4, "alpha")
sage: k.polynomial_ring()
Univariate Polynomial Ring in alpha over Finite Field of size 3

random_element( self, [bound=None])

A random element of the finite field.

INPUT:
    bound -- ignored

sage: k = GF(2**10, 'a')
sage: k.random_element()
a^9 + a

unit_group_exponent( self)

The exponent of the unit group of the finite field. For a finite field, this is always the order minus 1.

sage: k = GF(2**10)
sage: k.order()
1024
sage: k.unit_group_exponent()
1023

zeta( self, [n=None])

Returns an element of multiplicative order n in this this finite field, if there is one. Raises a ValueError if there is not.

sage: k = GF(7)
sage: k.zeta()
3
sage: k.zeta().multiplicative_order()
6
sage: k.zeta(3)
2
sage: k.zeta(3).multiplicative_order()
3
sage: k = GF(49)
sage: k.zeta().multiplicative_order()
48
sage: k.zeta(6)
3

Special Functions: __cmp__,$  $ __iter__,$  $ _gap_init_,$  $ _latex_

__cmp__( self, other)

Compares this finite field with other. Two finite fields are equal if and only if they have the same cardinality *and* the defining polynomials are the same.

sage: FiniteField(3**2) == FiniteField(3**3)
False
sage: FiniteField(3**2) == FiniteField(3**2)
True
sage: FiniteField(3**2,'beta') == FiniteField(3**2,'alpha')
False
sage: FiniteField(3**2,'beta') == FiniteField(3**2,'beta')
True

Class: FiniteField_prime_modn

class FiniteField_prime_modn
FiniteField_prime_modn( self, p, [name=None])

Functions: characteristic,$  $ degree,$  $ gen,$  $ is_prime,$  $ is_prime_field,$  $ modulus,$  $ order,$  $ polynomial

degree( self)

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

sage: FiniteField(3).degree()
1
sage: FiniteField(3**20).degree()
20

Special Functions: __iter__,$  $ __repr__,$  $ _coerce_,$  $ _is_valid_homomorphism_

See About this document... for information on suggesting changes.