Finite field elements implemented via PARI’s FFELT type
AUTHORS:
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
Return the characteristic polynomial of self.
INPUT:
EXAMPLE:
sage: R.<x> = PolynomialRing(FiniteField(3))
sage: F.<a> = FiniteField(3^2, modulus=x^2 + 1)
sage: a.charpoly('y')
y^2 + 1
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
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
Return True if self is non-zero.
EXAMPLE:
sage: F.<a> = FiniteField(5^3, impl='pari_ffelt')
sage: a.is_unit()
True
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
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
Return a discrete logarithm of self with respect to the given base.
INPUT:
OUTPUT:
An integer such that self equals base raised to
the power
. If no such
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
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
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
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
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