Base class for finite field elements#

AUTHORS:

  • David Roe (2010-01-14): factored out of sage.structure.element

  • Sebastian Oehms (2018-07-19): added conjugate() (see github issue #26761)

class sage.rings.finite_rings.element_base.Cache_base#

Bases: SageObject

fetch_int(number)#

Given an integer less than \(p^n\) with base \(2\) representation \(a_0 + a_1 \cdot 2 + \cdots + a_k 2^k\), this returns \(a_0 + a_1 x + \cdots + a_k x^k\), where \(x\) is the generator of this finite field.

EXAMPLES:

sage: k.<a> = GF(2^48)
sage: k._cache.fetch_int(2^33 + 2 + 1)                                      # needs sage.libs.ntl
a^33 + a + 1
class sage.rings.finite_rings.element_base.FinitePolyExtElement#

Bases: FiniteRingElement

Elements represented as polynomials modulo a given ideal.

additive_order()#

Return the additive order of this finite field element.

EXAMPLES:

sage: k.<a> = FiniteField(2^12, 'a')
sage: b = a^3 + a + 1
sage: b.additive_order()
2
sage: k(0).additive_order()
1
charpoly(var='x', algorithm='pari')#

Return the characteristic polynomial of self as a polynomial with given variable.

INPUT:

  • var – string (default: ‘x’)

  • algorithm – string (default: 'pari')

    • 'pari' – use pari’s charpoly

    • 'matrix' – return the charpoly computed from the matrix of left multiplication by self

The result is not cached.

EXAMPLES:

sage: from sage.rings.finite_rings.element_base import FinitePolyExtElement
sage: k.<a> = FiniteField(19^2)
sage: parent(a)
Finite Field in a of size 19^2
sage: b = a**20
sage: p = FinitePolyExtElement.charpoly(b, "x", algorithm="pari")
sage: q = FinitePolyExtElement.charpoly(b, "x", algorithm="matrix")         # needs sage.modules
sage: q == p                                                                # needs sage.modules
True
sage: p
x^2 + 15*x + 4
sage: factor(p)
(x + 17)^2
sage: b.minpoly('x')
x + 17
conjugate()#

This methods returns the result of the Frobenius morphism in the case where the field is a quadratic extension, say \(GF(q^2)\), where \(q=p^k\) is a prime power and \(p\) the characteristic of the field.

OUTPUT:

Instance of this class representing the image under the Frobenius morphisms.

EXAMPLES:

sage: F.<a> = GF(16)
sage: b = a.conjugate(); b
a + 1
sage: a == b.conjugate()
True

sage: F.<a> = GF(27)
sage: a.conjugate()
Traceback (most recent call last):
...
TypeError: cardinality of the field must be a square number
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 C int type)

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

EXAMPLES:

sage: F.<a> = GF(29^2)
sage: z = a^2 + 5*a + 1
sage: z.pth_power()
19*a + 20
sage: z.pth_power(10)
10*a + 28
sage: z.pth_power(-10) == z
True
sage: F.<b> = GF(2^12)
sage: y = b^3 + b + 1
sage: y == (y.pth_power(-3))^(2^3)
True
sage: y.pth_power(2)
b^7 + b^6 + b^5 + b^4 + b^3 + b
integer_representation(*args, **kwds)#

Deprecated: Use to_integer() instead. See github issue #33941 for details.

is_square()#

Returns True if and only if this element is a perfect square.

EXAMPLES:

sage: k.<a> = FiniteField(9, impl='givaro', modulus='primitive')            # needs sage.libs.linbox
sage: a.is_square()                                                         # needs sage.libs.linbox
False
sage: (a**2).is_square()                                                    # needs sage.libs.linbox
True
sage: k.<a> = FiniteField(4, impl='ntl', modulus='primitive')               # needs sage.libs.ntl
sage: (a**2).is_square()                                                    # needs sage.libs.ntl
True
sage: k.<a> = FiniteField(17^5, impl='pari_ffelt', modulus='primitive')     # needs sage.libs.pari
sage: a.is_square()                                                         # needs sage.libs.pari
False
sage: (a**2).is_square()                                                    # needs sage.libs.pari
True

sage: k(0).is_square()                                                      # needs sage.libs.linbox
True
list()#

Return the list of coefficients (in little-endian) of this finite field element when written as a polynomial in the generator.

Equivalent to calling list() on this element.

EXAMPLES:

sage: x = polygen(GF(71))
sage: F.<u> = GF(71^7, modulus=x^7 + x + 1)
sage: a = 3 + u + 3*u^2 + 3*u^3 + 7*u^4
sage: a.list()
[3, 1, 3, 3, 7, 0, 0]
sage: a.list() == list(a) == [a[i] for i in range(F.degree())]
True

The coefficients returned are those of a fully reduced representative of the finite field element:

sage: b = u^777
sage: b.list()
[9, 69, 4, 27, 40, 10, 56]
sage: (u.polynomial()^777).list()
[0, 0, 0, 0, ..., 0, 1]
matrix(reverse=False)#

Return the matrix of left multiplication by the element on the power basis \(1, x, x^2, \ldots, x^{d-1}\) for the field extension.

Thus the emph{columns} of this matrix give the images of each of the \(x^i\).

INPUT:

  • reverse – if True, act on vectors in reversed order

EXAMPLES:

sage: # needs sage.modules
sage: k.<a> = GF(2^4)
sage: b = k.random_element()
sage: vector(a*b) == a.matrix() * vector(b)
True
sage: (a*b)._vector_(reverse=True) == a.matrix(reverse=True) * b._vector_(reverse=True)
True
minimal_polynomial(var='x')#

Returns the minimal polynomial of this element (over the corresponding prime subfield).

EXAMPLES:

sage: k.<a> = FiniteField(3^4)
sage: parent(a)
Finite Field in a of size 3^4
sage: b=a**20;p=charpoly(b,"y");p
y^4 + 2*y^2 + 1
sage: factor(p)
(y^2 + 1)^2
sage: b.minimal_polynomial('y')
y^2 + 1
minpoly(var='x', algorithm='pari')#

Returns the minimal polynomial of this element (over the corresponding prime subfield).

INPUT:

  • var - string (default: ‘x’)

  • algorithm - string (default: ‘pari’)

    • ‘pari’ – use pari’s minpoly

    • ‘matrix’ – return the minpoly computed from the matrix of left multiplication by self

EXAMPLES:

sage: from sage.rings.finite_rings.element_base import FinitePolyExtElement
sage: k.<a> = FiniteField(19^2)
sage: parent(a)
Finite Field in a of size 19^2
sage: b=a**20
sage: p=FinitePolyExtElement.minpoly(b,"x", algorithm="pari")
sage: q=FinitePolyExtElement.minpoly(b,"x", algorithm="matrix")
sage: q == p
True
sage: p
x + 17
multiplicative_order()#

Return the multiplicative order of this field element.

EXAMPLES:

sage: S.<a> = GF(5^3); S
Finite Field in a of size 5^3
sage: a.multiplicative_order()
124
sage: (a^8).multiplicative_order()
31
sage: S(0).multiplicative_order()
Traceback (most recent call last):
...
ArithmeticError: Multiplicative order of 0 not defined.
norm()#

Return the norm of self down to the prime subfield.

This is the product of the Galois conjugates of self.

EXAMPLES:

sage: S.<b> = GF(5^2); S
Finite Field in b of size 5^2
sage: b.norm()
2
sage: b.charpoly('t')
t^2 + 4*t + 2

Next we consider a cubic extension:

sage: S.<a> = GF(5^3); S
Finite Field in a of size 5^3
sage: a.norm()
2
sage: a.charpoly('t')
t^3 + 3*t + 3
sage: a * a^5 * (a^25)
2
nth_root(n, extend=False, all=False, algorithm=None, cunningham=False)#

Returns an \(n\)th root of self.

INPUT:

  • n – integer \(\geq 1\)

  • extend – bool (default: False); if True, return an \(n\)th root in an extension ring, if necessary. Otherwise, raise a ValueError if the root is not in the base ring. Warning: this option is not implemented!

  • all – bool (default: False); if True, return all \(n\)th roots of self, instead of just one.

  • algorithm – string (default: None); ‘Johnston’ is the only currently supported option. For IntegerMod elements, the problem is reduced to the prime modulus case using CRT and \(p\)-adic logs, and then this algorithm used.

OUTPUT:

If self has an \(n\)th root, returns one (if all is False) or a list of all of them (if all is True). Otherwise, raises a ValueError (if extend is False) or a NotImplementedError (if extend is True).

Warning

The extend option is not implemented (yet).

EXAMPLES:

sage: K = GF(31)
sage: a = K(22)
sage: K(22).nth_root(7)
13
sage: K(25).nth_root(5)
5
sage: K(23).nth_root(3)
29

sage: K.<a> = GF(625)
sage: (3*a^2+a+1).nth_root(13)**13
3*a^2 + a + 1

sage: k.<a> = GF(29^2)
sage: b = a^2 + 5*a + 1
sage: b.nth_root(11)
3*a + 20
sage: b.nth_root(5)
Traceback (most recent call last):
...
ValueError: no nth root
sage: b.nth_root(5, all = True)
[]
sage: b.nth_root(3, all = True)
[14*a + 18, 10*a + 13, 5*a + 27]

sage: k.<a> = GF(29^5)
sage: b = a^2 + 5*a + 1
sage: b.nth_root(5)
19*a^4 + 2*a^3 + 2*a^2 + 16*a + 3
sage: b.nth_root(7)
Traceback (most recent call last):
...
ValueError: no nth root
sage: b.nth_root(4, all=True)
[]

ALGORITHM:

The default is currently an algorithm described in [Joh1999].

AUTHOR:

  • David Roe (2010-02-13)

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 C int type)

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

EXAMPLES:

sage: F.<a> = GF(29^2)
sage: z = a^2 + 5*a + 1
sage: z.pth_power()
19*a + 20
sage: z.pth_power(10)
10*a + 28
sage: z.pth_power(-10) == z
True
sage: F.<b> = GF(2^12)
sage: y = b^3 + b + 1
sage: y == (y.pth_power(-3))^(2^3)
True
sage: y.pth_power(2)
b^7 + b^6 + b^5 + b^4 + b^3 + b
pth_root(k=1)#

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

INPUT:

  • k – integer (default: 1, must fit in C int type)

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

EXAMPLES:

sage: F.<b> = GF(2^12)
sage: y = b^3 + b + 1
sage: y == (y.pth_root(3))^(2^3)
True
sage: y.pth_root(2)
b^11 + b^10 + b^9 + b^7 + b^5 + b^4 + b^2 + b
sqrt(extend=False, all=False)#

See square_root().

EXAMPLES:

sage: k.<a> = GF(3^17)
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
square_root(extend=False, all=False)#

The square root function.

INPUT:

  • extend – bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the root is not in the base ring.

    Warning

    This option is not implemented!

  • all – bool (default: False); if True, return all square roots of self, instead of just one.

Warning

The 'extend' option is not implemented (yet).

EXAMPLES:

sage: F = FiniteField(7^2, 'a')
sage: F(2).square_root()
4
sage: F(3).square_root()
2*a + 6
sage: F(3).square_root()**2
3
sage: F(4).square_root()
2
sage: K = FiniteField(7^3, 'alpha', impl='pari_ffelt')
sage: K(3).square_root()
Traceback (most recent call last):
...
ValueError: must be a perfect square.
to_bytes(byteorder='big')#

Return an array of bytes representing an integer.

Internally relies on the python int.to_bytes() method. Length of byte array is determined from the field’s order.

INPUT:

  • byteorder – str (default: "big"); determines the byte order of the output; can only be "big" or "little"

EXAMPLES:

sage: F.<z5> = GF(3^5)
sage: a = z5^4 + 2*z5^3 + 1
sage: a.to_bytes()
b'\x88'

sage: F.<z3> = GF(163^3)
sage: a = 136*z3^2 + 10*z3 + 125
sage: a.to_bytes()
b'7)\xa3'
to_integer(reverse=False)#

Return an integer representation of this finite field element obtained by lifting its representative polynomial to \(\ZZ\) and evaluating it at the characteristic \(p\).

If reverse is set to True (default: False), the list of coefficients is reversed prior to evaluation.

Inverse of sage.rings.finite_rings.finite_field_base.FiniteField.from_integer().

EXAMPLES:

sage: F.<t> = GF(7^5)
sage: F(5).to_integer()
5
sage: t.to_integer()
7
sage: (t^2).to_integer()
49
sage: (t^2+1).to_integer()
50
sage: (t^2+t+1).to_integer()
57

sage: F.<t> = GF(2^8)
sage: u = F.from_integer(0xd1)
sage: bin(u.to_integer(False))
'0b11010001'
sage: bin(u.to_integer(True))
'0b10001011'
trace()#

Return the trace of this element, which is the sum of the Galois conjugates.

EXAMPLES:

sage: S.<a> = GF(5^3); S
Finite Field in a of size 5^3
sage: a.trace()
0
sage: a.charpoly('t')
t^3 + 3*t + 3
sage: a + a^5 + a^25
0
sage: z = a^2 + a + 1
sage: z.trace()
2
sage: z.charpoly('t')
t^3 + 3*t^2 + 2*t + 2
sage: z + z^5 + z^25
2
class sage.rings.finite_rings.element_base.FiniteRingElement#

Bases: CommutativeRingElement

to_bytes(byteorder='big')#

Return an array of bytes representing an integer.

Internally relies on the python int.to_bytes() method. Length of byte array is determined from the field’s order.

INPUT:

  • byteorder – str (default: "big"); determines the byte order of input_bytes; can only be "big" or "little"

EXAMPLES:

sage: F = GF(65537)
sage: a = F(8726)
sage: a.to_bytes()
b'
sage.rings.finite_rings.element_base.is_FiniteFieldElement(x)#

Return True if x is a finite field element.

This function is deprecated.

EXAMPLES:

sage: from sage.rings.finite_rings.element_base import is_FiniteFieldElement
sage: is_FiniteFieldElement(1)
doctest:...: DeprecationWarning: the function is_FiniteFieldElement is deprecated; use isinstance(x, sage.structure.element.FieldElement) and x.parent().is_finite() instead
See https://github.com/sagemath/sage/issues/32664 for details.
False
sage: is_FiniteFieldElement(IntegerRing())
False
sage: is_FiniteFieldElement(GF(5)(2))
True