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: 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'>
>>> 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[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 modulusrepr
– (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
); ifTrue
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 mostorder()
elements are created.
OUTPUT: Givaro finite field with characteristic \(p\) and cardinality \(p^n\)
EXAMPLES:
By default Conway polynomials are used:
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
For binary fields, you may ask for a minimal weight polynomial:
sage: k = GF(2**10, 'a', modulus='minimal_weight') sage: k.modulus() x^10 + x^3 + 1
>>> 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)[source]¶
Return
a*b - c
.INPUT:
a
,b
,c
–FiniteField_givaroElement
EXAMPLES:
sage: k.<a> = GF(3**3) sage: k._cache.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._cache.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
andb
first and addingc
to the result.INPUT:
a
,b
,c
–FiniteField_givaroElement
EXAMPLES:
sage: k.<a> = GF(2**8) sage: k._cache.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._cache.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:
a
,b
,c
–FiniteField_givaroElement
EXAMPLES:
sage: k.<a> = GF(3**3) sage: k._cache.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._cache.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^3,'a')._cache.characteristic(); p 19
>>> from sage.all import * >>> p = GF(Integer(19)**Integer(3),'a')._cache.characteristic(); p 19
- element_from_data(e)[source]¶
Coerces several data types to
self
.INPUT:
e
– data to coerce in
EXAMPLES:
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
>>> 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()[source]¶
Return the degree of this field over \(\GF{p}\).
EXAMPLES:
sage: K.<a> = GF(9); K._cache.exponent() 2
>>> from sage.all import * >>> K = GF(Integer(9), names=('a',)); (a,) = K._first_ngens(1); K._cache.exponent() 2
- fetch_int(number)[source]¶
Given an integer
n
return a finite field element inself
which equalsn
under the condition thatgen()
is set tocharacteristic()
.EXAMPLES:
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
>>> 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()[source]¶
Return a generator of the field.
EXAMPLES:
sage: K.<a> = GF(625) sage: K._cache.gen() a
>>> from sage.all import * >>> K = GF(Integer(625), names=('a',)); (a,) = K._first_ngens(1) >>> K._cache.gen() a
- 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._cache.int_to_log(4) 228 sage: k._cache.int_to_log(3) 57 sage: k.gen()^57 3
>>> 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)[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._cache.log_to_int(4) 16 sage: k._cache.log_to_int(20) 180
>>> 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()[source]¶
Return the order of this field.
EXAMPLES:
sage: K.<a> = GF(9) sage: K._cache.order() 9
>>> from sage.all import * >>> K = GF(Integer(9), names=('a',)); (a,) = K._first_ngens(1) >>> K._cache.order() 9
- order_c()[source]¶
Return the order of this field.
EXAMPLES:
sage: K.<a> = GF(9) sage: K._cache.order_c() 9
>>> from sage.all import * >>> K = GF(Integer(9), names=('a',)); (a,) = K._first_ngens(1) >>> K._cache.order_c() 9
- random_element(*args, **kwds)[source]¶
Return a random element of
self
.EXAMPLES:
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
>>> 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
- class sage.rings.finite_rings.element_givaro.FiniteField_givaroElement[source]¶
Bases:
FinitePolyExtElement
An element of a (Givaro) finite field.
- is_one()[source]¶
Return
True
ifself == k(1)
.EXAMPLES:
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
>>> 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()[source]¶
Return
True
ifself
is a square inself.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: 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]
>>> 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()[source]¶
Return
True
ifself
is nonzero, so it is a unit as an element of the finite field.EXAMPLES:
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
>>> 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)[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 elementorder
– integer (optional), multiple of order ofbase
check
– boolean (default:False
): If set, test whether the givenorder
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: k.<b> = GF(5^2); k Finite Field in b of size 5^2 sage: a = b^7 sage: a.log(b) 7
>>> 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()[source]¶
Return the multiplicative order of this field element.
EXAMPLES:
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
>>> 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)[source]¶
Return
self
viewed as a polynomial overself.parent().prime_subfield()
.EXAMPLES:
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
>>> 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)[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
); ifTrue
, return a square root in an extension ring, if necessary. Otherwise, raise aValueError
if the root is not in the base ring.Warning
this option is not implemented!
all
– boolean (default:False
); ifTrue
, return all square roots ofself
, 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: 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.
>>> 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[source]¶
Bases:
object
Iterator over
FiniteField_givaro
elements. We iterate multiplicatively, as powers of a fixed internal generator.EXAMPLES:
sage: for x in GF(2^2,'a'): print(x) 0 a a + 1 1
>>> 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)[source]¶
EXAMPLES:
sage: k = GF(3**7, 'a') sage: loads(dumps(k)) == k # indirect doctest True
>>> from sage.all import * >>> k = GF(Integer(3)**Integer(7), 'a') >>> loads(dumps(k)) == k # indirect doctest True