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

Multivariate 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 if self 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 if self 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 if self is non-zero.

EXAMPLES:

sage: F.<a> = FiniteField(5^3, impl='pari_ffelt')
sage: a.is_unit()
True
is_zero()

Return True if self 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 equals base raised to the power \(x\). If no such \(x\) exists, a ValueError 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. If all is True, a list containing all square roots of self (of length zero, one or two) is returned instead.

If extend is True, a square root is chosen in an extension field if necessary. If extend is False, 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