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.

EXAMPLE:

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

TESTS:

sage: n = 63
sage: m = 3;
sage: K.<a> = GF(2^n, impl='pari_ffelt')
sage: f = conway_polynomial(2, n)
sage: f(a) == 0
True
sage: e = (2^n - 1) / (2^m - 1)
sage: conway_polynomial(2, m)(a^e) == 0
True

sage: K.<a> = FiniteField(2^16, impl='pari_ffelt')
sage: K(0).is_zero()
True
sage: (a - a).is_zero()
True
sage: a - a
0
sage: a == a
True
sage: a - a == 0
True
sage: a - a == K(0)
True
sage: TestSuite(a).run()

Test creating elements from basic Python types:

sage: K.<a> = FiniteField(7^20, impl='pari_ffelt')
sage: K(int(8))
1
sage: K(long(-2^300))
6

charpoly(var='x')¶

Return the characteristic polynomial of self.

INPUT:

var – string (default: ‘x’): variable name to use.

EXAMPLE:

sage: R.<x> = PolynomialRing(FiniteField(3))
sage: F.<a> = FiniteField(3^2, modulus=x^2 + 1)
sage: a.charpoly('y')
y^2 + 1

is_one()¶

Return True if self equals 1.

EXAMPLE:

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.

EXAMPLE:

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

is_zero()¶

Return True if self equals 0.

EXAMPLE:

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.

EXAMPLE:

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

multiplicative_order()¶

Returns the order of self in the multiplicative group.

EXAMPLE:

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

polynomial()¶

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.

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()
alpha^2 + 1
sage: (a**2 + 1).polynomial().parent()
Univariate Polynomial Ring in alpha 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()
5*a + 1
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)¶

EXAMPLE:

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

Navigation

Finite field elements implemented via PARI’s FFELT type¶

Previous topic

Next topic

This Page

Quick search

Navigation