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)                                                     # needs sage.libs.ntl
<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)                                                     # needs sage.libs.ntl
<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'>

Sage Live

k = GF(5); type(k)
k = GF(5^2,'c'); type(k)
k = GF(2^16,'c'); type(k)                                                     # needs sage.libs.ntl
k = GF(3^16,'c'); type(k)
n = previous_prime_power(2^16 - 1)
while is_prime(n):
 n = previous_prime_power(n)
factor(n)
k = GF(n,'c'); type(k)

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[source]¶

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

Sage Live

k.<a> = GF(2**8)
-a ^ k.degree()
f = k.modulus(); f

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

Sage Live

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

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

Sage Live

k = GF(3**5, 'a', modulus='random')
k.modulus() # random polynomial

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

Sage

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

Python

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

Sage Live

k = GF(2**10, 'a', modulus='minimal_weight')                          # needs sage.libs.m4ri sage.libs.ntl
k.modulus()                                                           # needs sage.libs.m4ri sage.libs.ntl

a_times_b_minus_c(a, b, c)[source]¶

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

Sage Live

k.<a> = GF(3**3)
k._cache.a_times_b_minus_c(a,a,k(1))

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:

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

Sage Live

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

c_minus_a_times_b(a, b, c)[source]¶

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

Sage Live

k.<a> = GF(3**3)
k._cache.c_minus_a_times_b(a,a,k(1))

characteristic()[source]¶

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

Sage Live

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

element_from_data(e)[source]¶

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                               # needs sage.modules
(0, 1, 0, 0, 0, 0, 0, 0)
sage: k(e)  # indirect doctest                                              # needs sage.modules
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                               # needs sage.modules
(0, 1, 0, 0, 0, 0, 0, 0)
>>> k(e)  # indirect doctest                                              # needs sage.modules
a

Sage Live

k = GF(3^8, 'a')
type(k)
e = k.vector_space(map=False).gen(1); e                               # needs sage.modules
k(e)  # indirect doctest                                              # needs sage.modules

exponent()[source]¶

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

Sage Live

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

fetch_int(number)[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

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

Sage Live

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

gen()[source]¶

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

Sage Live

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

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

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

Sage Live

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

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

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

Sage Live

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

order()[source]¶

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

Sage Live

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

order_c()[source]¶

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

Sage Live

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

random_element(*args, **kwds)[source]¶

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

Sage Live

k = GF(23**3, 'a')
e = k._cache.random_element()
e.parent() is k
type(e)
P.<x> = PowerSeriesRing(GF(3^3, 'a'))
P.random_element(5).parent() is P

repr[source]¶

class sage.rings.finite_rings.element_givaro.FiniteField_givaroElement[source]¶

Bases: FinitePolyExtElement

An element of a (Givaro) finite field.

Internal implementation detail: self.element is a cdef int member such that:

if self.element == 0, then self.is_zero(),
otherwise, self == g^self.element where g is a multiplicative generator.

In Givaro code, the type of element is known by the typename Rep.

It is preferred to use the exposed interface of Givaro than to rely on this implementation detail.

The C function make_FiniteField_givaroElement() can be internally used to construct a FiniteField_givaroElement() object given int element.

is_one()[source]¶

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

Sage Live

k.<a> = GF(3^4); k
a.is_one()
k(1).is_one()

is_square()[source]¶

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]

Sage Live

k.<a> = GF(9); k
a.is_square()
v = set([x^2 for x in k])
[x.is_square() for x in v]
[x.is_square() for x in k if not x in v]

is_unit()[source]¶

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

Sage Live

k.<a> = GF(3^4); k
a.is_unit()
k(0).is_unit()

log(base, order=None, check=False)[source]¶

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. This is only for backwards compatibility, it is not used in the current implementation.
check – boolean (default: False): If set, test whether the given order is correct.

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

Sage Live

k.<b> = GF(5^2); k
a = b^7
a.log(b)

multiplicative_order()[source]¶

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

Sage Live

S.<b> = GF(5^2); S
b.multiplicative_order()
(b^6).multiplicative_order()

polynomial(name=None)[source]¶

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)                                                               # needs sage.libs.flint
<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)                                                               # needs sage.libs.flint
<class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
>>> parent(f)
Univariate Polynomial Ring in b over Finite Field of size 5

Sage Live

k.<b> = GF(5^2); k
f = (b^2+1).polynomial(); f
type(f)                                                               # needs sage.libs.flint
parent(f)

sqrt(extend=False, all=False)[source]¶

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

Sage Live

k.<a> = GF(7^2)
k(2).sqrt()
k(3).sqrt()
k(3).sqrt()**2
k(4).sqrt()
k.<a> = GF(7^3)
k(3).sqrt()

class sage.rings.finite_rings.element_givaro.FiniteField_givaro_iterator[source]¶

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 Live

for x in GF(2^2,'a'): print(x)

sage.rings.finite_rings.element_givaro.unpickle_Cache_givaro(parent, p, k, modulus, rep, cache)[source]¶

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 Live

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

sage.rings.finite_rings.element_givaro.unpickle_FiniteField_givaroElement(parent, x)[source]¶