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

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

Finite field elements implemented via PARI’s FFELT type¶

Previous topic

Next topic

This Page