Finite field elements implemented via PARI’s FFELT type¶
AUTHORS:
- Peter Bruin (June 2013): initial version, based on element_ext_pari.py by William Stein et al. and element_ntl_gf2e.pyx by Martin Albrecht.
-
class
sage.rings.finite_rings.element_pari_ffelt.
FiniteFieldElement_pari_ffelt
¶ Bases:
sage.rings.finite_rings.element_base.FinitePolyExtElement
An element of a finite field implemented using PARI.
EXAMPLES:
sage: K = FiniteField(10007^10, 'a', impl='pari_ffelt') sage: a = K.gen(); a a sage: type(a) <type 'sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt'>
sage: k = FiniteField(3^4, 'a', impl='pari_ffelt') sage: b = k(5) # indirect doctest sage: b.parent() Finite Field in a of size 3^4 sage: a = k.gen() sage: k(a + 2) a + 2
Univariate polynomials coerce into finite fields by evaluating the polynomial at the field’s generator:
sage: R.<x> = QQ[] sage: k.<a> = FiniteField(5^2, 'a', impl='pari_ffelt') sage: k(R(2/3)) 4 sage: k(x^2) a + 3 sage: R.<x> = GF(5)[] sage: k(x^3-2*x+1) 2*a + 4 sage: x = polygen(QQ) sage: k(x^25) a sage: Q.<q> = FiniteField(5^7, 'q', impl='pari_ffelt') sage: L = GF(5) sage: LL.<xx> = L[] sage: Q(xx^2 + 2*xx + 4) q^2 + 2*q + 4 sage: k = FiniteField(3^11, 't', impl='pari_ffelt') sage: k.polynomial() t^11 + 2*t^2 + 1 sage: P = k.polynomial_ring() sage: k(P.0^11) t^2 + 2
An element can be specified by its vector of coordinates with respect to the basis consisting of powers of the generator:
sage: k = FiniteField(3^11, ‘t’, impl=’pari_ffelt’) sage: V = k.vector_space() sage: V Vector space of dimension 11 over Finite Field of size 3 sage: v = V([0,1,2,0,1,2,0,1,2,0,1]) sage: k(v) t^10 + 2*t^8 + t^7 + 2*t^5 + t^4 + 2*t^2 + tMultivariate polynomials only coerce if constant:
sage: k = FiniteField(5^2, 'a', impl='pari_ffelt') sage: R = k['x,y,z']; R Multivariate Polynomial Ring in x, y, z over Finite Field in a of size 5^2 sage: k(R(2)) 2 sage: R = QQ['x,y,z'] sage: k(R(1/5)) Traceback (most recent call last): ... ZeroDivisionError: inverse of Mod(0, 5) does not exist
Gap elements can also be coerced into finite fields:
sage: F = FiniteField(2^3, 'a', impl='pari_ffelt') sage: a = F.multiplicative_generator(); a a sage: b = gap(a^3); b Z(2^3)^3 sage: F(b) a + 1 sage: a^3 a + 1 sage: a = GF(13)(gap('0*Z(13)')); a 0 sage: a.parent() Finite Field of size 13 sage: F = FiniteField(2^4, 'a', impl='pari_ffelt') sage: F(gap('Z(16)^3')) a^3 sage: F(gap('Z(16)^2')) a^2
You can also call a finite extension field with a string to produce an element of that field, like this:
sage: k = GF(2^8, 'a') sage: k('a^200') a^4 + a^3 + a^2
This is especially useful for conversion from Singular etc.
-
charpoly
(var='x')¶ Return the characteristic polynomial of
self
.INPUT:
var
– string (default: ‘x’): variable name to use.
EXAMPLES:
sage: R.<x> = PolynomialRing(FiniteField(3)) sage: F.<a> = FiniteField(3^2, modulus=x^2 + 1, impl='pari_ffelt') sage: a.charpoly('y') y^2 + 1
-
is_one
()¶ Return
True
ifself
equals 1.EXAMPLES:
sage: F.<a> = FiniteField(5^3, impl='pari_ffelt') sage: a.is_one() False sage: (a/a).is_one() True
-
is_square
()¶ Return
True
if and only ifself
is a square in the finite field.EXAMPLES:
sage: k.<a> = FiniteField(3^2, impl='pari_ffelt') sage: a.is_square() False sage: (a**2).is_square() True sage: k.<a> = FiniteField(2^2, impl='pari_ffelt') sage: (a**2).is_square() True sage: k.<a> = FiniteField(17^5, impl='pari_ffelt') sage: (a**2).is_square() True sage: a.is_square() False sage: k(0).is_square() True
-
is_unit
()¶ Return
True
ifself
is non-zero.EXAMPLES:
sage: F.<a> = FiniteField(5^3, impl='pari_ffelt') sage: a.is_unit() True
-
is_zero
()¶ Return
True
ifself
equals 0.EXAMPLES:
sage: F.<a> = FiniteField(5^3, impl='pari_ffelt') sage: a.is_zero() False sage: (a - a).is_zero() True
-
lift
()¶ If
self
is an element of the prime field, return a lift of this element to an integer.EXAMPLES:
sage: k = FiniteField(next_prime(10^10)^2, 'u', impl='pari_ffelt') sage: a = k(17)/k(19) sage: b = a.lift(); b 7894736858 sage: b.parent() Integer Ring
-
log
(base)¶ Return a discrete logarithm of
self
with respect to the given base.INPUT:
base
– non-zero field element
OUTPUT:
An integer \(x\) such that
self
equalsbase
raised to the power \(x\). If no such \(x\) exists, aValueError
is raised.EXAMPLES:
sage: F.<g> = FiniteField(2^10, impl='pari_ffelt') sage: b = g; a = g^37 sage: a.log(b) 37 sage: b^37; a g^8 + g^7 + g^4 + g + 1 g^8 + g^7 + g^4 + g + 1
sage: F.<a> = FiniteField(5^2, impl='pari_ffelt') sage: F(-1).log(F(2)) 2 sage: F(1).log(a) 0
Some cases where the logarithm is not defined or does not exist:
sage: F.<a> = GF(3^10, impl='pari_ffelt') sage: a.log(-1) Traceback (most recent call last): ... ArithmeticError: element a does not lie in group generated by 2 sage: a.log(0) Traceback (most recent call last): ... ArithmeticError: discrete logarithm with base 0 is not defined sage: F(0).log(1) Traceback (most recent call last): ... ArithmeticError: discrete logarithm of 0 is not defined
-
minpoly
(var='x')¶ Return the minimal polynomial of
self
.INPUT:
var
– string (default: ‘x’): variable name to use.
EXAMPLES:
sage: R.<x> = PolynomialRing(FiniteField(3)) sage: F.<a> = FiniteField(3^2, modulus=x^2 + 1, impl='pari_ffelt') sage: a.minpoly('y') y^2 + 1
-
multiplicative_order
()¶ Returns the order of
self
in the multiplicative group.EXAMPLES:
sage: a = FiniteField(5^3, 'a', impl='pari_ffelt').0 sage: a.multiplicative_order() 124 sage: a**124 1
-
polynomial
(name=None)¶ Return the unique representative of
self
as a polynomial over the prime field whose degree is less than the degree of the finite field over its prime field.INPUT:
name
– (optional) variable name
EXAMPLES:
sage: k.<a> = FiniteField(3^2, impl='pari_ffelt') sage: pol = a.polynomial() sage: pol a sage: parent(pol) Univariate Polynomial Ring in a over Finite Field of size 3
sage: k = FiniteField(3^4, 'alpha', impl='pari_ffelt') sage: a = k.gen() sage: a.polynomial() alpha sage: (a**2 + 1).polynomial('beta') beta^2 + 1 sage: (a**2 + 1).polynomial().parent() Univariate Polynomial Ring in alpha over Finite Field of size 3 sage: (a**2 + 1).polynomial('beta').parent() Univariate Polynomial Ring in beta over Finite Field of size 3
-
sqrt
(extend=False, all=False)¶ Return a square root of
self
, if it exists.INPUT:
extend
– bool (default:False
)Warning
This option is not implemented.
all
- bool (default:False
)
OUTPUT:
A square root of
self
, if it exists. Ifall
isTrue
, a list containing all square roots ofself
(of length zero, one or two) is returned instead.If
extend
isTrue
, a square root is chosen in an extension field if necessary. Ifextend
isFalse
, a ValueError is raised if the element is not a square in the base field.Warning
The
extend
option is not implemented (yet).EXAMPLES:
sage: F = FiniteField(7^2, 'a', impl='pari_ffelt') sage: F(2).sqrt() 4 sage: F(3).sqrt() in (2*F.gen() + 6, 5*F.gen() + 1) True sage: F(3).sqrt()**2 3 sage: F(4).sqrt(all=True) [2, 5] sage: K = FiniteField(7^3, 'alpha', impl='pari_ffelt') sage: K(3).sqrt() Traceback (most recent call last): ... ValueError: element is not a square sage: K(3).sqrt(all=True) [] sage: K.<a> = GF(3^17, impl='pari_ffelt') sage: (a^3 - a - 1).sqrt() a^16 + 2*a^15 + a^13 + 2*a^12 + a^10 + 2*a^9 + 2*a^8 + a^7 + a^6 + 2*a^5 + a^4 + 2*a^2 + 2*a + 2
-
-
sage.rings.finite_rings.element_pari_ffelt.
unpickle_FiniteFieldElement_pari_ffelt
(parent, elem)¶ EXAMPLES:
sage: k.<a> = GF(2^20, impl='pari_ffelt') sage: e = k.random_element() sage: f = loads(dumps(e)) # indirect doctest sage: e == f True