Base class for finite field elements

AUTHORS:

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

• Sebastian Oehms (2018-7-19): added conjugate() (see trac ticket #26761)

class sage.rings.finite_rings.element_base.Cache_base

Bases: sage.structure.sage_object.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)
a^33 + a + 1

class sage.rings.finite_rings.element_base.FinitePolyExtElement

Bases: sage.rings.finite_rings.element_base.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")
sage: q == p
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

is_square()

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

EXAMPLES:

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

sage: k(0).is_square()
True

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: 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)
[]

ALGORITHMS:

• The default is currently an algorithm described in the following paper:

Johnston, Anna M. A generalized qth root algorithm. Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms. Baltimore, 1999: pp 929-930.

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.

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: sage.structure.element.CommutativeRingElement

sage.rings.finite_rings.element_base.is_FiniteFieldElement(x)

Returns if x is a finite field element.

EXAMPLES:

sage: from sage.rings.finite_rings.element_base import is_FiniteFieldElement
sage: is_FiniteFieldElement(1)
False
sage: is_FiniteFieldElement(IntegerRing())
False
sage: is_FiniteFieldElement(GF(5)(2))
True