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: 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)
<class 'sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt'>
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
frobenius(k=1)#

Return the \((p^k)^{th}\) power of self, where \(p\) is the characteristic of the field.

INPUT:

  • k – integer (default: 1); must fit in a C int

Note that if \(k\) is negative, then this computes the appropriate root.

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, order=None, check=False)#

Return a discrete logarithm of self with respect to the given base.

INPUT:

  • base – non-zero field element

  • order – integer (optional), the order of the base

  • check – boolean (optional, default False): If set, test whether the given order is correct.

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

sage: p = 2^127-1
sage: F.<t> = GF((p, 3))
sage: elt = F.random_element()^(p^2+p+1)
sage: (elt^2).log(elt, p-1)
2

Passing the order argument can lead to huge speedups when factoring the order of the entire unit group is expensive but the order of the base element is much smaller:

sage: %timeit (elt^2).log(elt)       # not tested
6.18 s ± 85 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit (elt^2).log(elt, p-1)  # not tested
147 ms ± 1.39 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

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
pth_power(k=1)#

Return the \((p^k)^{th}\) power of self, where \(p\) is the characteristic of the field.

INPUT:

  • k – integer (default: 1); must fit in a C int

Note that if \(k\) is negative, then this computes the appropriate root.

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: # needs sage.modules
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