Givaro finite field elements

Sage includes the Givaro finite field library, for highly optimized arithmetic in finite fields.

Note

The arithmetic is performed by the Givaro C++ library which uses Zech logs internally to represent finite field elements. This implementation is the default finite extension field implementation in Sage for the cardinality less than \(2^{16}\), as it is a lot faster than the PARI implementation. Some functionality in this class however is implemented using PARI.

EXAMPLES:

Sage

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'>

sage: n = previous_prime_power(2^16 - 1)
sage: while is_prime(n):
....:  n = previous_prime_power(n)
sage: factor(n)
251^2
sage: k = GF(n,'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>

Python

>>> from sage.all import *
>>> k = GF(Integer(5)); type(k)
<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>
>>> k = GF(Integer(5)**Integer(2),'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
>>> k = GF(Integer(2)**Integer(16),'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e_with_category'>
>>> k = GF(Integer(3)**Integer(16),'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt_with_category'>

>>> n = previous_prime_power(Integer(2)**Integer(16) - Integer(1))
>>> while is_prime(n):
...  n = previous_prime_power(n)
>>> factor(n)
251^2
>>> k = GF(n,'c'); type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>

AUTHORS:

• Martin Albrecht <malb@informatik.uni-bremen.de> (2006-06-05)

• William Stein (2006-12-07): editing, lots of docs, etc.

• Robert Bradshaw (2007-05-23): is_square/sqrt, pow.

class sage.rings.finite_rings.element_givaro.Cache_givaro

Bases: Cache_base

Finite Field.

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

INPUT:

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

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

• modulus – a polynomial to use as modulus

• 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 – boolean (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:

Sage

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

Python

>>> 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

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

Python

>>> 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

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

Python

>>> 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

For binary fields, you may ask for a minimal weight polynomial:

Sage

sage: k = GF(2**10, 'a', modulus='minimal_weight')
sage: k.modulus()
x^10 + x^3 + 1

Python

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(10), 'a', modulus='minimal_weight')
>>> k.modulus()
x^10 + x^3 + 1

a_times_b_minus_c(a, b, c)

Return a*b - c.

INPUT:

• a, b, c – FiniteField_givaroElement

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.a_times_b_minus_c(a,a,k(Integer(1)))
a^2 + 2

a_times_b_plus_c(a, b, c)

Return a*b + c.

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

INPUT:

• a, b, c – FiniteField_givaroElement

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.a_times_b_plus_c(a,a,k(Integer(1)))
a^2 + 1

c_minus_a_times_b(a, b, c)

Return c - a*b.

INPUT:

• a, b, c – FiniteField_givaroElement

EXAMPLES:

Sage

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

Python

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

characteristic()

Return the characteristic of this field.

EXAMPLES:

Sage

sage: p = GF(19^3,'a')._cache.characteristic(); p
19

Python

>>> from sage.all import *
>>> p = GF(Integer(19)**Integer(3),'a')._cache.characteristic(); p
19

element_from_data(e)

Coerces several data types to self.

INPUT:

• e – data to coerce in

EXAMPLES:

Sage

sage: k = GF(3^8, 'a')
sage: type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: e = k.vector_space(map=False).gen(1); e
(0, 1, 0, 0, 0, 0, 0, 0)
sage: k(e) #indirect doctest
a

Python

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(8), 'a')
>>> type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
>>> e = k.vector_space(map=False).gen(Integer(1)); e
(0, 1, 0, 0, 0, 0, 0, 0)
>>> k(e) #indirect doctest
a

exponent()

Return the degree of this field over \(\GF{p}\).

EXAMPLES:

Sage

sage: K.<a> = GF(9); K._cache.exponent()
2

Python

>>> from sage.all import *
>>> K = GF(Integer(9), names=('a',)); (a,) = K._first_ngens(1); K._cache.exponent()
2

fetch_int(number)

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

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

Python

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), names=('a',)); (a,) = k._first_ngens(1)
>>> k._cache.fetch_int(Integer(8))
a^3
>>> e = k._cache.fetch_int(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()

Return a generator of the field.

EXAMPLES:

Sage

sage: K.<a> = GF(625)
sage: K._cache.gen()
a

Python

>>> from sage.all import *
>>> K = GF(Integer(625), names=('a',)); (a,) = K._first_ngens(1)
>>> K._cache.gen()
a

int_to_log(n)

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

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

Python

>>> from sage.all import *
>>> k = GF(Integer(7)**Integer(3), 'a')
>>> k._cache.int_to_log(Integer(4))
228
>>> k._cache.int_to_log(Integer(3))
57
>>> k.gen()**Integer(57)
3

log_to_int(n)

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

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

Python

>>> from sage.all import *
>>> k = GF(Integer(2)**Integer(8), 'a')
>>> k._cache.log_to_int(Integer(4))
16
>>> k._cache.log_to_int(Integer(20))
180

order()

Return the order of this field.

EXAMPLES:

Sage

sage: K.<a> = GF(9)
sage: K._cache.order()
9

Python

>>> from sage.all import *
>>> K = GF(Integer(9), names=('a',)); (a,) = K._first_ngens(1)
>>> K._cache.order()
9

order_c()

Return the order of this field.

EXAMPLES:

Sage

sage: K.<a> = GF(9)
sage: K._cache.order_c()
9

Python

>>> from sage.all import *
>>> K = GF(Integer(9), names=('a',)); (a,) = K._first_ngens(1)
>>> K._cache.order_c()
9

random_element(*args, **kwds)

Return a random element of self.

EXAMPLES:

Sage

sage: k = GF(23**3, 'a')
sage: e = k._cache.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

Python

>>> from sage.all import *
>>> k = GF(Integer(23)**Integer(3), 'a')
>>> e = k._cache.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

repr

class sage.rings.finite_rings.element_givaro.FiniteField_givaroElement

Bases: FinitePolyExtElement

An element of a (Givaro) finite field.

is_one()

Return True if self == k(1).

EXAMPLES:

Sage

sage: k.<a> = GF(3^4); k
Finite Field in a of size 3^4
sage: a.is_one()
False
sage: k(1).is_one()
True

Python

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(4), names=('a',)); (a,) = k._first_ngens(1); k
Finite Field in a of size 3^4
>>> a.is_one()
False
>>> k(Integer(1)).is_one()
True

is_square()

Return True if self is a square in self.parent().

ALGORITHM:

Elements are stored as powers of generators, so we simply check to see if it is an even power of a generator.

EXAMPLES:

Sage

sage: k.<a> = GF(9); k
Finite Field in a of size 3^2
sage: a.is_square()
False
sage: v = set([x^2 for x in k])
sage: [x.is_square() for x in v]
[True, True, True, True, True]
sage: [x.is_square() for x in k if not x in v]
[False, False, False, False]

Python

>>> from sage.all import *
>>> k = GF(Integer(9), names=('a',)); (a,) = k._first_ngens(1); k
Finite Field in a of size 3^2
>>> a.is_square()
False
>>> v = set([x**Integer(2) for x in k])
>>> [x.is_square() for x in v]
[True, True, True, True, True]
>>> [x.is_square() for x in k if not x in v]
[False, False, False, False]

is_unit()

Return True if self is nonzero, so it is a unit as an element of the finite field.

EXAMPLES:

Sage

sage: k.<a> = GF(3^4); k
Finite Field in a of size 3^4
sage: a.is_unit()
True
sage: k(0).is_unit()
False

Python

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(4), names=('a',)); (a,) = k._first_ngens(1); k
Finite Field in a of size 3^4
>>> a.is_unit()
True
>>> k(Integer(0)).is_unit()
False

log(base, order=None, check=False)

Return the log to the base \(b\) of self, i.e., an integer \(n\) such that \(b^n =\) self.

INPUT:

• base – non-zero field element

• order – integer (optional), multiple of order of base

• check – boolean (default: False): If set, test whether the given order is correct.

Warning

TODO – This is currently implemented by solving the discrete log problem – which shouldn’t be needed because of how finite field elements are represented.

EXAMPLES:

Sage

sage: k.<b> = GF(5^2); k
Finite Field in b of size 5^2
sage: a = b^7
sage: a.log(b)
7

Python

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(2), names=('b',)); (b,) = k._first_ngens(1); k
Finite Field in b of size 5^2
>>> a = b**Integer(7)
>>> a.log(b)
7

multiplicative_order()

Return the multiplicative order of this field element.

EXAMPLES:

Sage

sage: S.<b> = GF(5^2); S
Finite Field in b of size 5^2
sage: b.multiplicative_order()
24
sage: (b^6).multiplicative_order()
4

Python

>>> from sage.all import *
>>> S = GF(Integer(5)**Integer(2), names=('b',)); (b,) = S._first_ngens(1); S
Finite Field in b of size 5^2
>>> b.multiplicative_order()
24
>>> (b**Integer(6)).multiplicative_order()
4

polynomial(name=None)

Return self viewed as a polynomial over self.parent().prime_subfield().

EXAMPLES:

Sage

sage: k.<b> = GF(5^2); k
Finite Field in b of size 5^2
sage: f = (b^2+1).polynomial(); f
b + 4
sage: type(f)
<class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
sage: parent(f)
Univariate Polynomial Ring in b over Finite Field of size 5

Python

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(2), names=('b',)); (b,) = k._first_ngens(1); k
Finite Field in b of size 5^2
>>> f = (b**Integer(2)+Integer(1)).polynomial(); f
b + 4
>>> type(f)
<class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
>>> parent(f)
Univariate Polynomial Ring in b over Finite Field of size 5

sqrt(extend=False, all=False)

Return a square root of this finite field element in its parent, if there is one. Otherwise, raise a ValueError.

INPUT:

• extend – boolean (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the root is not in the base ring.

  Warning

  this option is not implemented!

• all – boolean (default: False); if True, return all square roots of self, instead of just one

Warning

The extend option is not implemented (yet).

ALGORITHM:

self is stored as \(a^k\) for some generator \(a\). Return \(a^{k/2}\) for even \(k\).

EXAMPLES:

Sage

sage: k.<a> = GF(7^2)
sage: k(2).sqrt()
3
sage: k(3).sqrt()
2*a + 6
sage: k(3).sqrt()**2
3
sage: k(4).sqrt()
2
sage: k.<a> = GF(7^3)
sage: k(3).sqrt()
Traceback (most recent call last):
...
ValueError: must be a perfect square.

Python

>>> from sage.all import *
>>> k = GF(Integer(7)**Integer(2), names=('a',)); (a,) = k._first_ngens(1)
>>> k(Integer(2)).sqrt()
3
>>> k(Integer(3)).sqrt()
2*a + 6
>>> k(Integer(3)).sqrt()**Integer(2)
3
>>> k(Integer(4)).sqrt()
2
>>> k = GF(Integer(7)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> k(Integer(3)).sqrt()
Traceback (most recent call last):
...
ValueError: must be a perfect square.

class sage.rings.finite_rings.element_givaro.FiniteField_givaro_iterator

Bases: object

Iterator over FiniteField_givaro elements. We iterate multiplicatively, as powers of a fixed internal generator.

EXAMPLES:

Sage

sage: for x in GF(2^2,'a'): print(x)
0
a
a + 1
1

Python

>>> from sage.all import *
>>> for x in GF(Integer(2)**Integer(2),'a'): print(x)
0
a
a + 1
1

sage.rings.finite_rings.element_givaro.unpickle_Cache_givaro(parent, p, k, modulus, rep, cache)

EXAMPLES:

Sage

sage: k = GF(3**7, 'a')
sage: loads(dumps(k)) == k # indirect doctest
True

Python

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(7), 'a')
>>> loads(dumps(k)) == k # indirect doctest
True

sage.rings.finite_rings.element_givaro.unpickle_FiniteField_givaroElement(parent, x)