Sage supports arithmetic in finite prime and extension fields.
Several implementation for prime fields are implemented natively in
Sage for several sizes of primes . These implementations
are
Small extension fields of cardinality are
implemented using tables of Zech logs via the Givaro C++ library
(sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro).
While this representation is very fast it is limited to finite
fields of small cardinality. Larger finite extension fields of
order
are internally represented as
polynomials over smaller finite prime fields. If the
characteristic of such a field is 2 then NTL is used internally to
represent the field
(sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e).
In all other case the PARI C library is used
(sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari).
However, this distinction is internal only and the user usually does not have to worry about it because consistency across all implementations is aimed for. In all extension field implementations the user may either specify a minimal polynomial or leave the choice to Sage.
For small finite fields the default choice are Conway polynomials.
The Conway polynomial is the lexicographically first
monic irreducible, primitive polynomial of degree
over
with the property that for a root
of
we have that
is a root of
for all
dividing
. Sage
contains a database of Conway polynomials which also can be queried
independently of finite field construction.
While Sage supports basic arithmetic in finite fields some more advanced features for computing with finite fields are still not implemented. For instance, Sage does not calculate embeddings of finite fields yet.
EXAMPLES:
sage: k = GF(5); type(k)
<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>
sage: k = GF(5^2,'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: k = GF(2^16,'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e_with_category'>
sage: k = GF(3^16,'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt_with_category'>
Finite Fields support iteration, starting with 0.
sage: k = GF(9, 'a')
sage: for i,x in enumerate(k): print i,x
0 0
1 a
2 a + 1
3 2*a + 1
4 2
5 2*a
6 2*a + 2
7 a + 2
8 1
sage: for a in GF(5):
... print a
0
1
2
3
4
We output the base rings of several finite fields.
sage: k = GF(3); type(k)
<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>
sage: k.base_ring()
Finite Field of size 3
sage: k = GF(9,'alpha'); type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: k.base_ring()
Finite Field of size 3
sage: k = GF(3^40,'b'); type(k)
<class 'sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt_with_category'>
sage: k.base_ring()
Finite Field of size 3
Further examples:
sage: GF(2).is_field()
True
sage: GF(next_prime(10^20)).is_field()
True
sage: GF(19^20,'a').is_field()
True
sage: GF(8,'a').is_field()
True
AUTHORS:
Bases: sage.structure.factory.UniqueFactory
Return the globally unique finite field of given order with generator labeled by the given name and possibly with given modulus.
INPUT:
ALIAS: You can also use GF instead of FiniteField – they are identical.
EXAMPLES:
sage: k.<a> = FiniteField(9); k
Finite Field in a of size 3^2
sage: parent(a)
Finite Field in a of size 3^2
sage: charpoly(a, 'y')
y^2 + 2*y + 2
We illustrate the proof flag. The following example would hang for a very long time if we didn’t use proof=False.
Note
Magma only supports proof=False for making finite fields, so falsely appears to be faster than Sage – see :trac:10975.
sage: k = FiniteField(10^1000 + 453, proof=False)
sage: k = FiniteField((10^1000 + 453)^2, 'a', proof=False) # long time -- about 5 seconds
sage: F.<x> = GF(5)[]
sage: K.<a> = GF(5**5, name='a', modulus=x^5 - x +1 )
sage: f = K.modulus(); f
x^5 + 4*x + 1
sage: type(f)
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
The modulus must be irreducible:
sage: K.<a> = GF(5**5, name='a', modulus=x^5 - x)
Traceback (most recent call last):
...
ValueError: finite field modulus must be irreducible but it is not.
You can’t accidentally fool the constructor into thinking the
modulus is irreducible when it is not, since it actually tests
irreducibility modulo . Also, the modulus has to be of the
right degree:
sage: F.<x> = QQ[]
sage: factor(x^5 + 2)
x^5 + 2
sage: K.<a> = GF(5**5, name='a', modulus=x^5 + 2)
Traceback (most recent call last):
...
ValueError: finite field modulus must be irreducible but it is not.
sage: K.<a> = GF(5**5, name='a', modulus=x^3 + 3*x + 3)
Traceback (most recent call last):
...
ValueError: The degree of the modulus does not correspond to the
cardinality of the field.
If you wish to live dangerously, you can tell the constructor not to test irreducibility using check_irreducible=False, but this can easily lead to crashes and hangs – so do not do it unless you know that the modulus really is irreducible and has the correct degree!
sage: F.<x> = GF(5)[]
sage: K.<a> = GF(5**2, name='a', modulus=x^2 + 2, check_irreducible=False)
sage: L = GF(3**2, name='a', modulus=QQ[x](x - 1), check_irreducible=False)
sage: L.list() # random
[0, a, 1, 2, 1, 2, 1, 2, 1]
The order of a finite field must be a prime power:
sage: GF(1)
Traceback (most recent call last):
...
ValueError: the order of a finite field must be > 1.
sage: GF(100)
Traceback (most recent call last):
...
ValueError: the order of a finite field must be a prime power.
Finite fields with explicit random modulus are not cached:
sage: k.<a> = GF(5**10, modulus='random')
sage: n.<a> = GF(5**10, modulus='random')
sage: n is k
False
sage: GF(5**10, 'a') is GF(5**10, 'a')
True
We check that various ways of creating the same finite field yield the same object, which is cached:
sage: K = GF(7, 'a')
sage: L = GF(7, 'b')
sage: K is L
True
sage: K = GF(4,'a'); K.modulus()
x^2 + x + 1
sage: L = GF(4,'a', K.modulus())
sage: K is L
True
sage: M = GF(4,'a', K.modulus().change_variable_name('y'))
sage: K is M
True
You may print finite field elements as integers. This currently
only works if the order of field is , though:
sage: k.<a> = GF(2^8, repr='int')
sage: a
2
The following demonstrate coercions for finite fields using Conway polynomials:
sage: k = GF(5^2, conway=True, prefix='z'); a = k.gen()
sage: l = GF(5^5, conway=True, prefix='z'); b = l.gen()
sage: a + b
3*z10^5 + z10^4 + z10^2 + 3*z10 + 1
Note that embeddings are compatible in lattices of such finite fields:
sage: m = GF(5^3, conway=True, prefix='z'); c = m.gen()
sage: (a+b)+c == a+(b+c)
True
sage: (a*b)*c == a*(b*c)
True
sage: from sage.categories.pushout import pushout
sage: n = pushout(k, l)
sage: o = pushout(l, m)
sage: q = pushout(n, o)
sage: q(o(b)) == q(n(b))
True
Another check that embeddings are defined properly:
sage: k = GF(3**10, conway=True, prefix='z')
sage: l = GF(3**20, conway=True, prefix='z')
sage: l(k.gen()**10) == l(k.gen())**10
True
EXAMPLES:
sage: GF.create_key_and_extra_args(9, 'a')
((9, ('a',), x^2 + 2*x + 2, None, '{}', 3, 2, True), {})
sage: GF.create_key_and_extra_args(9, 'a', foo='value')
((9, ('a',), x^2 + 2*x + 2, None, "{'foo': 'value'}", 3, 2, True), {'foo': 'value'})
EXAMPLES:
sage: K = GF(19) # indirect doctest
sage: TestSuite(K).run()
EXAMPLES:
sage: key, extra = GF.create_key_and_extra_args(9, 'a'); key
(9, ('a',), x^2 + 2*x + 2, None, '{}', 3, 2, True)
sage: K = GF.create_object(0, key); K
Finite Field in a of size 3^2
sage: GF.other_keys(key, K)
[(9, ('a',), x^2 + 2*x + 2, None, '{}', 3, 2, True),
(9, ('a',), x^2 + 2*x + 2, 'givaro', '{}', 3, 2, True)]
Returns True if x is a prime finite field.
EXAMPLES:
sage: from sage.rings.finite_rings.constructor import is_PrimeFiniteField
sage: is_PrimeFiniteField(QQ)
False
sage: is_PrimeFiniteField(GF(7))
True
sage: is_PrimeFiniteField(GF(7^2,'a'))
False
sage: is_PrimeFiniteField(GF(next_prime(10^90,proof=False)))
True