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'>
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
– (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
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
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
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
- a_times_b_minus_c(a, b, c)#
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
- a_times_b_plus_c(a, b, c)#
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
- c_minus_a_times_b(a, b, c)#
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
- characteristic()#
Return the characteristic of this field.
EXAMPLES:
sage: p = GF(19^3,'a')._cache.characteristic(); p 19
- element_from_data(e)#
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
- exponent()#
Return the degree of this field over \(\GF{p}\).
EXAMPLES:
sage: K.<a> = GF(9); K._cache.exponent() 2
- fetch_int(number)#
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
- gen()#
Return a generator of the field.
EXAMPLES:
sage: K.<a> = GF(625) sage: 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 an 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
- 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: k = GF(2**8, 'a') sage: k._cache.log_to_int(4) 16 sage: k._cache.log_to_int(20) 180
- order()#
Return the order of this field.
EXAMPLES:
sage: K.<a> = GF(9) sage: K._cache.order() 9
- order_c()#
Return the order of this field.
EXAMPLES:
sage: K.<a> = GF(9) sage: K._cache.order_c() 9
- random_element(*args, **kwds)#
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
- repr#
- class sage.rings.finite_rings.element_givaro.FiniteField_givaroElement#
Bases:
FinitePolyExtElement
An element of a (Givaro) finite field.
- is_one()#
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
- is_square()#
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]
- is_unit()#
Return
True
if self 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
- log(base)#
Return the log to the base \(b\) of
self
, i.e., an integer \(n\) such that \(b^n =\)self
.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
- multiplicative_order()#
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
- polynomial(name=None)#
Return self viewed as a polynomial over
self.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
- 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
– bool (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
– bool (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.
- 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: for x in GF(2^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: k = GF(3**7, 'a') sage: loads(dumps(k)) == k # indirect doctest True
- sage.rings.finite_rings.element_givaro.unpickle_FiniteField_givaroElement(parent, x)#