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[source]¶

Bases: FinitePolyExtElement

An element of a finite field implemented using PARI.

EXAMPLES:

Sage

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'>

Python

>>> from sage.all import *
>>> K = FiniteField(Integer(10007)**Integer(10), 'a', impl='pari_ffelt')
>>> a = K.gen(); a
a
>>> type(a)
<class 'sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt'>

charpoly(var='x')[source]¶

Return the characteristic polynomial of self.

INPUT:

var – string (default: 'x'); variable name to use

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(FiniteField(Integer(3)), names=('x',)); (x,) = R._first_ngens(1)
>>> F = FiniteField(Integer(3)**Integer(2), modulus=x**Integer(2) + Integer(1), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> a.charpoly('y')
y^2 + 1

frobenius(k=1)[source]¶

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()[source]¶

Return True if self equals 1.

EXAMPLES:

Sage

sage: F.<a> = FiniteField(5^3, impl='pari_ffelt')
sage: a.is_one()
False
sage: (a/a).is_one()
True

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(5)**Integer(3), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> a.is_one()
False
>>> (a/a).is_one()
True

is_square()[source]¶

Return True if and only if self is a square in the finite field.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> k = FiniteField(Integer(3)**Integer(2), impl='pari_ffelt', names=('a',)); (a,) = k._first_ngens(1)
>>> a.is_square()
False
>>> (a**Integer(2)).is_square()
True

>>> k = FiniteField(Integer(2)**Integer(2), impl='pari_ffelt', names=('a',)); (a,) = k._first_ngens(1)
>>> (a**Integer(2)).is_square()
True

>>> k = FiniteField(Integer(17)**Integer(5), impl='pari_ffelt', names=('a',)); (a,) = k._first_ngens(1)
>>> (a**Integer(2)).is_square()
True
>>> a.is_square()
False
>>> k(Integer(0)).is_square()
True

is_unit()[source]¶

Return True if self is nonzero.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(5)**Integer(3), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> a.is_unit()
True

is_zero()[source]¶

Return True if self equals 0.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(5)**Integer(3), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> a.is_zero()
False
>>> (a - a).is_zero()
True

lift()[source]¶

If self is an element of the prime field, return a lift of this element to an integer.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> k = FiniteField(next_prime(Integer(10)**Integer(10))**Integer(2), 'u', impl='pari_ffelt')
>>> a = k(Integer(17))/k(Integer(19))
>>> b = a.lift(); b
7894736858
>>> b.parent()
Integer Ring

log(base, order=None, check=False)[source]¶

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

INPUT:

base – nonzero field element
order – integer (optional), the order of the base
check – boolean (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

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

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(2)**Integer(10), impl='pari_ffelt', names=('g',)); (g,) = F._first_ngens(1)
>>> b = g; a = g**Integer(37)
>>> a.log(b)
37
>>> b**Integer(37); a
g^8 + g^7 + g^4 + g + 1
g^8 + g^7 + g^4 + g + 1

Sage

sage: F.<a> = FiniteField(5^2, impl='pari_ffelt')
sage: F(-1).log(F(2))
2
sage: F(1).log(a)
0

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(5)**Integer(2), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> F(-Integer(1)).log(F(Integer(2)))
2
>>> F(Integer(1)).log(a)
0

Sage

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

Python

>>> from sage.all import *
>>> p = Integer(2)**Integer(127)-Integer(1)
>>> F = GF((p, Integer(3)), names=('t',)); (t,) = F._first_ngens(1)
>>> elt = F.random_element()**(p**Integer(2)+p+Integer(1))
>>> (elt**Integer(2)).log(elt, p-Integer(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

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)

Python

>>> from sage.all import *
>>> %timeit (elt**Integer(2)).log(elt)       # not tested
6.18 s ± 85 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit (elt**Integer(2)).log(elt, p-Integer(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

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

Python

>>> from sage.all import *
>>> F = GF(Integer(3)**Integer(10), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> a.log(-Integer(1))
Traceback (most recent call last):
...
ArithmeticError: element a does not lie in group generated by 2
>>> a.log(Integer(0))
Traceback (most recent call last):
...
ArithmeticError: discrete logarithm with base 0 is not defined
>>> F(Integer(0)).log(Integer(1))
Traceback (most recent call last):
...
ArithmeticError: discrete logarithm of 0 is not defined

minpoly(var='x')[source]¶

Return the minimal polynomial of self.

INPUT:

var – string (default: 'x'); variable name to use

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = PolynomialRing(FiniteField(Integer(3)), names=('x',)); (x,) = R._first_ngens(1)
>>> F = FiniteField(Integer(3)**Integer(2), modulus=x**Integer(2) + Integer(1), impl='pari_ffelt', names=('a',)); (a,) = F._first_ngens(1)
>>> a.minpoly('y')
y^2 + 1

multiplicative_order()[source]¶

Return the order of self in the multiplicative group.

EXAMPLES:

Sage

sage: a = FiniteField(5^3, 'a', impl='pari_ffelt').0
sage: a.multiplicative_order()
124
sage: a**124
1

Python

>>> from sage.all import *
>>> a = FiniteField(Integer(5)**Integer(3), 'a', impl='pari_ffelt').gen(0)
>>> a.multiplicative_order()
124
>>> a**Integer(124)
1

polynomial(name=None)[source]¶

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

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

Python

>>> from sage.all import *
>>> k = FiniteField(Integer(3)**Integer(2), impl='pari_ffelt', names=('a',)); (a,) = k._first_ngens(1)
>>> pol = a.polynomial()
>>> pol
a
>>> parent(pol)
Univariate Polynomial Ring in a over Finite Field of size 3

Sage

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

Python

>>> from sage.all import *
>>> k = FiniteField(Integer(3)**Integer(4), 'alpha', impl='pari_ffelt')
>>> a = k.gen()
>>> a.polynomial()
alpha
>>> (a**Integer(2) + Integer(1)).polynomial('beta')
beta^2 + 1
>>> (a**Integer(2) + Integer(1)).polynomial().parent()
Univariate Polynomial Ring in alpha over Finite Field of size 3
>>> (a**Integer(2) + Integer(1)).polynomial('beta').parent()
Univariate Polynomial Ring in beta over Finite Field of size 3

pth_power(k=1)[source]¶

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)[source]¶

Return a square root of self, if it exists.

INPUT:

extend – boolean (default: False)

Warning

This option is not implemented.
all – boolean (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

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

Python

>>> from sage.all import *
>>> F = FiniteField(Integer(7)**Integer(2), 'a', impl='pari_ffelt')
>>> F(Integer(2)).sqrt()
4
>>> F(Integer(3)).sqrt() in (Integer(2)*F.gen() + Integer(6), Integer(5)*F.gen() + Integer(1))
True
>>> F(Integer(3)).sqrt()**Integer(2)
3
>>> F(Integer(4)).sqrt(all=True)
[2, 5]

>>> K = FiniteField(Integer(7)**Integer(3), 'alpha', impl='pari_ffelt')
>>> K(Integer(3)).sqrt()
Traceback (most recent call last):
...
ValueError: element is not a square
>>> K(Integer(3)).sqrt(all=True)
[]

>>> K = GF(Integer(3)**Integer(17), impl='pari_ffelt', names=('a',)); (a,) = K._first_ngens(1)
>>> (a**Integer(3) - a - Integer(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)[source]¶

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> k = GF(Integer(2)**Integer(20), impl='pari_ffelt', names=('a',)); (a,) = k._first_ngens(1)
>>> e = k.random_element()
>>> f = loads(dumps(e)) # indirect doctest
>>> e == f
True