Givaro finite fields#

Finite fields that are implemented using Zech logs and the cardinality must be less than \(2^{16}\). By default, Conway polynomials are used as minimal polynomial.

class sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro(q, name='a', modulus=None, repr='poly', cache=False)[source]#

Bases: FiniteField

Finite field implemented using Zech logs and the cardinality must be less than \(2^{16}\). By default, Conway polynomials are used as minimal polynomials.

INPUT:

  • q – \(p^n\) (must be prime power)

  • name – (default: 'a') variable used for poly_repr()

  • modulus – A minimal polynomial to use for reduction.

  • repr – (default: 'poly') controls the way elements are printed to the user:

    • ‘log’: repr is log_repr()

    • ‘int’: repr is int_repr()

    • ‘poly’: repr is poly_repr()

  • cache – (default: False) if True a cache of all elements of this field is created. Thus, arithmetic does not create new elements which speeds calculations up. Also, if many elements are needed during a calculation this cache reduces the memory requirement as at most order() elements are created.

OUTPUT:

Givaro finite field with characteristic \(p\) and cardinality \(p^n\).

EXAMPLES:

By default, Conway polynomials are used for extension fields:

sage: k.<a> = GF(2**8)
sage: -a ^ k.degree()
a^4 + a^3 + a^2 + 1
sage: f = k.modulus(); f
x^8 + x^4 + x^3 + x^2 + 1

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), names=('a',)); (a,) = k._first_ngens(1)
>>> -a ** k.degree()
a^4 + a^3 + a^2 + 1
>>> f = k.modulus(); f
x^8 + x^4 + x^3 + x^2 + 1

You may enforce a modulus:

sage: P.<x> = PolynomialRing(GF(2))
sage: f = x^8 + x^4 + x^3 + x + 1 # Rijndael Polynomial
sage: k.<a> = GF(2^8, modulus=f)
sage: k.modulus()
x^8 + x^4 + x^3 + x + 1
sage: a^(2^8)
a

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(2)), names=('x',)); (x,) = P._first_ngens(1)
>>> f = x**Integer(8) + x**Integer(4) + x**Integer(3) + x + Integer(1) # Rijndael Polynomial
>>> k = GF(Integer(2)**Integer(8), modulus=f, names=('a',)); (a,) = k._first_ngens(1)
>>> k.modulus()
x^8 + x^4 + x^3 + x + 1
>>> a**(Integer(2)**Integer(8))
a

You may enforce a random modulus:

sage: k = GF(3**5, 'a', modulus='random')
sage: k.modulus() # random polynomial
x^5 + 2*x^4 + 2*x^3 + x^2 + 2

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(5), 'a', modulus='random')
>>> k.modulus() # random polynomial
x^5 + 2*x^4 + 2*x^3 + x^2 + 2

Three different representations are possible:

sage: FiniteField(9, 'a', impl='givaro', repr='poly').gen()
a
sage: FiniteField(9, 'a', impl='givaro', repr='int').gen()
3
sage: FiniteField(9, 'a', impl='givaro', repr='log').gen()
1

>>> from sage.all import *
>>> FiniteField(Integer(9), 'a', impl='givaro', repr='poly').gen()
a
>>> FiniteField(Integer(9), 'a', impl='givaro', repr='int').gen()
3
>>> FiniteField(Integer(9), 'a', impl='givaro', repr='log').gen()
1

For prime fields, the default modulus is the polynomial \(x - 1\), but you can ask for a different modulus:

sage: GF(1009, impl='givaro').modulus()
x + 1008
sage: GF(1009, impl='givaro', modulus='conway').modulus()
x + 998

>>> from sage.all import *
>>> GF(Integer(1009), impl='givaro').modulus()
x + 1008
>>> GF(Integer(1009), impl='givaro', modulus='conway').modulus()
x + 998
a_times_b_minus_c(a, b, c)[source]#

Return a*b - c.

INPUT:

EXAMPLES:

sage: k.<a> = GF(3**3)
sage: k.a_times_b_minus_c(a,a,k(1))
a^2 + 2

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> k.a_times_b_minus_c(a,a,k(Integer(1)))
a^2 + 2
a_times_b_plus_c(a, b, c)[source]#

Return a*b + c. This is faster than multiplying a and b first and adding c to the result.

INPUT:

EXAMPLES:

sage: k.<a> = GF(2**8)
sage: k.a_times_b_plus_c(a,a,k(1))
a^2 + 1

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), names=('a',)); (a,) = k._first_ngens(1)
>>> k.a_times_b_plus_c(a,a,k(Integer(1)))
a^2 + 1
c_minus_a_times_b(a, b, c)[source]#

Return c - a*b.

INPUT:

EXAMPLES:

sage: k.<a> = GF(3**3)
sage: k.c_minus_a_times_b(a,a,k(1))
2*a^2 + 1

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> k.c_minus_a_times_b(a,a,k(Integer(1)))
2*a^2 + 1
characteristic()[source]#

Return the characteristic of this field.

EXAMPLES:

sage: p = GF(19^5,'a').characteristic(); p
19
sage: type(p)
<class 'sage.rings.integer.Integer'>

>>> from sage.all import *
>>> p = GF(Integer(19)**Integer(5),'a').characteristic(); p
19
>>> type(p)
<class 'sage.rings.integer.Integer'>
degree()[source]#

If the cardinality of self is \(p^n\), then this returns \(n\).

OUTPUT:

Integer – the degree

EXAMPLES:

sage: GF(3^4,'a').degree()
4

>>> from sage.all import *
>>> GF(Integer(3)**Integer(4),'a').degree()
4
fetch_int(*args, **kwds)[source]#

Deprecated: Use from_integer() instead. See Issue #33941 for details.

frobenius_endomorphism(n=1)[source]#

INPUT:

  • n – an integer (default: 1)

OUTPUT:

The \(n\)-th power of the absolute arithmetic Frobenius endomorphism on this finite field.

EXAMPLES:

sage: k.<t> = GF(3^5)
sage: Frob = k.frobenius_endomorphism(); Frob
Frobenius endomorphism t |--> t^3 on Finite Field in t of size 3^5

sage: a = k.random_element()
sage: Frob(a) == a^3
True

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(5), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism(); Frob
Frobenius endomorphism t |--> t^3 on Finite Field in t of size 3^5

>>> a = k.random_element()
>>> Frob(a) == a**Integer(3)
True

We can specify a power:

sage: k.frobenius_endomorphism(2)
Frobenius endomorphism t |--> t^(3^2) on Finite Field in t of size 3^5

>>> from sage.all import *
>>> k.frobenius_endomorphism(Integer(2))
Frobenius endomorphism t |--> t^(3^2) on Finite Field in t of size 3^5

The result is simplified if possible:

sage: k.frobenius_endomorphism(6)
Frobenius endomorphism t |--> t^3 on Finite Field in t of size 3^5
sage: k.frobenius_endomorphism(5)
Identity endomorphism of Finite Field in t of size 3^5

>>> from sage.all import *
>>> k.frobenius_endomorphism(Integer(6))
Frobenius endomorphism t |--> t^3 on Finite Field in t of size 3^5
>>> k.frobenius_endomorphism(Integer(5))
Identity endomorphism of Finite Field in t of size 3^5

Comparisons work:

sage: k.frobenius_endomorphism(6) == Frob
True
sage: from sage.categories.morphism import IdentityMorphism
sage: k.frobenius_endomorphism(5) == IdentityMorphism(k)
True

>>> from sage.all import *
>>> k.frobenius_endomorphism(Integer(6)) == Frob
True
>>> from sage.categories.morphism import IdentityMorphism
>>> k.frobenius_endomorphism(Integer(5)) == IdentityMorphism(k)
True

AUTHOR:

  • Xavier Caruso (2012-06-29)

from_integer(n)[source]#

Given an integer \(n\) return a finite field element in self which equals \(n\) under the condition that gen() is set to characteristic().

EXAMPLES:

sage: k.<a> = GF(2^8)
sage: k.from_integer(8)
a^3
sage: e = k.from_integer(151); e
a^7 + a^4 + a^2 + a + 1
sage: 2^7 + 2^4 + 2^2 + 2 + 1
151

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), names=('a',)); (a,) = k._first_ngens(1)
>>> k.from_integer(Integer(8))
a^3
>>> e = k.from_integer(Integer(151)); e
a^7 + a^4 + a^2 + a + 1
>>> Integer(2)**Integer(7) + Integer(2)**Integer(4) + Integer(2)**Integer(2) + Integer(2) + Integer(1)
151
gen(n=0)[source]#

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: k = GF(3^4, 'b'); k.gen()
b
sage: k.gen(1)
Traceback (most recent call last):
...
IndexError: only one generator
sage: F = FiniteField(31, impl='givaro')
sage: F.gen()
1

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(4), 'b'); k.gen()
b
>>> k.gen(Integer(1))
Traceback (most recent call last):
...
IndexError: only one generator
>>> F = FiniteField(Integer(31), impl='givaro')
>>> F.gen()
1
int_to_log(n)[source]#

Given an integer \(n\) this method returns \(i\) where \(i\) satisfies \(g^i = n \mod p\) where \(g\) is the generator and \(p\) is the characteristic of self.

INPUT:

  • n – integer representation of a finite field element

OUTPUT:

log representation of n

EXAMPLES:

sage: k = GF(7**3, 'a')
sage: k.int_to_log(4)
228
sage: k.int_to_log(3)
57
sage: k.gen()^57
3

>>> from sage.all import *
>>> k = GF(Integer(7)**Integer(3), 'a')
>>> k.int_to_log(Integer(4))
228
>>> k.int_to_log(Integer(3))
57
>>> k.gen()**Integer(57)
3
log_to_int(n)[source]#

Given an integer \(n\) this method returns i where i satisfies \(g^n = i\) where \(g\) is the generator of self; the result is interpreted as an integer.

INPUT:

  • n – log representation of a finite field element

OUTPUT:

integer representation of a finite field element.

EXAMPLES:

sage: k = GF(2**8, 'a')
sage: k.log_to_int(4)
16
sage: k.log_to_int(20)
180

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), 'a')
>>> k.log_to_int(Integer(4))
16
>>> k.log_to_int(Integer(20))
180
order()[source]#

Return the cardinality of this field.

OUTPUT:

Integer – the number of elements in self.

EXAMPLES:

sage: n = GF(19^5,'a').order(); n
2476099
sage: type(n)
<class 'sage.rings.integer.Integer'>

>>> from sage.all import *
>>> n = GF(Integer(19)**Integer(5),'a').order(); n
2476099
>>> type(n)
<class 'sage.rings.integer.Integer'>
prime_subfield()[source]#

Return the prime subfield \(\GF{p}\) of self if self is \(\GF{p^n}\).

EXAMPLES:

sage: GF(3^4, 'b').prime_subfield()
Finite Field of size 3

sage: S.<b> = GF(5^2); S
Finite Field in b of size 5^2
sage: S.prime_subfield()
Finite Field of size 5
sage: type(S.prime_subfield())
<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>

>>> from sage.all import *
>>> GF(Integer(3)**Integer(4), 'b').prime_subfield()
Finite Field of size 3

>>> S = GF(Integer(5)**Integer(2), names=('b',)); (b,) = S._first_ngens(1); S
Finite Field in b of size 5^2
>>> S.prime_subfield()
Finite Field of size 5
>>> type(S.prime_subfield())
<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>
random_element(*args, **kwds)[source]#

Return a random element of self.

EXAMPLES:

sage: k = GF(23**3, 'a')
sage: e = k.random_element()
sage: e.parent() is k
True
sage: type(e)
<class 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>

sage: P.<x> = PowerSeriesRing(GF(3^3, 'a'))
sage: P.random_element(5).parent() is P
True

>>> from sage.all import *
>>> k = GF(Integer(23)**Integer(3), 'a')
>>> e = k.random_element()
>>> e.parent() is k
True
>>> type(e)
<class 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>

>>> P = PowerSeriesRing(GF(Integer(3)**Integer(3), 'a'), names=('x',)); (x,) = P._first_ngens(1)
>>> P.random_element(Integer(5)).parent() is P
True