12.8 Elements of Finite Fields

Module: sage.rings.finite_field_element

sage: K = FiniteField(2)
sage: V = VectorSpace(K,3)
sage: w = V([0,1,2])
sage: K(1)*w
(0, 1, 0)

Class: FiniteFieldElement

class FiniteFieldElement
An element of a finite field.

Create elements by first defining the finite field F, then use the notation F(n), for n an integer. or let a = F.gen() and write the element in terms of a.

sage: K = GF(10007^10, 'a')
sage: a = K.gen(); a
a
sage: loads(a.dumps()) == a
True
sage: K = GF(10007)
sage: a = K(938); a
938
sage: loads(a.dumps()) == a
True
FiniteFieldElement( self, parent, value)

Create element of a finite field.

sage: k = GF(9)
sage: a = k(11); a
2
sage: a.parent()
Finite Field in a of size 3^2

Functions: charpoly,$  $ copy,$  $ is_square,$  $ lift,$  $ log,$  $ multiplicative_order,$  $ norm,$  $ order,$  $ polynomial,$  $ rational_reconstruction,$  $ trace

charpoly( self)

Returns the characteristic polynomial of this element.

sage: k = GF(3**3)
sage: a = k.gen()
sage: a.charpoly()
x^3 + 2*x + 1
sage: k.modulus()
x^3 + 2*x + 1
sage: b = a**2 + 1
sage: b.charpoly()
x^3 + x^2 + 2*x + 1

copy( self)

Return a copy of this element.

sage: k = GF(3**3)
sage: a = k(5)
sage: a
2
sage: a.copy()
2
sage: b = a.copy()
sage: a == b
True
sage: a is b
False
sage: a is a
True

is_square( self)

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

sage: k = GF(3**2)
sage: a = k.gen()
sage: a.is_square()
False
sage: (a**2).is_square()
True
sage: k = GF(2**2)
sage: a = k.gen()
sage: (a**2).is_square()
True
sage: k = GF(17**5); a = k.gen()
sage: (a**2).is_square()
True
sage: a.is_square()
False

lift( self)

If this element lies in a prime finite field, return a lift of this element to an integer.

sage: k = GF(next_prime(10**10))
sage: a = k(17)/k(19)
sage: b = a.lift(); b
7894736858
sage: b.parent()
Integer Ring

log( self, a)

Return $ x$ such that $ b^x = a$ , where $ b$ is self.

INPUT:
    self, a are elements of a finite field.

OUTPUT:
    Integer $x$ such that $a^x = b$, if it exists.
    Raises a ValueError exception if no such $x$ exists.

sage: F = GF(17)
sage: F(2).log(F(8))
3
sage: F = GF(113)
sage: F(2).log(F(81))
19
sage: F = GF(next_prime(10000))
sage: F(23).log(F(8111))
8393

sage: F = GF(2^10)
sage: g = F.gen()
sage: b = g; a = g^37
sage: b.log(a)
37
sage: b^37; a
a^8 + a^7 + a^4 + a + 1
a^8 + a^7 + a^4 + a + 1

Author: David Joyner and William Stein (2005-11)

multiplicative_order( self)

Returns the multiplicative order of this element, which must be nonzero.

sage: a = GF(5**3, 'a').0
sage: a.multiplicative_order()
124
sage: a**124
1

norm( self)

Returns the norm of this element, which is the constant term of the characteristic polynomial, i.e., the determinant of left multiplication.

sage: k = GF(3**3); a = k.gen()
sage: b = a**2 + 2
sage: b.charpoly()
x^3 + x^2 + 2
sage: b.trace()
2
sage: b.norm()
2

order( self)

Return the additive order of this finite field element.

polynomial( self)

Elements of a finite field are represented as a polynomial modulo a modulus. This functions returns the representating polynomial as an element of the polynomial ring over the prime finite field, with the same variable as the finite field.

The default variable is a:

sage: k = GF(3**2)
sage: k.gen().polynomial()
a

The variable can be any string.

sage: k = FiniteField(3**4, "alpha")
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

rational_reconstruction( self)

If the parent field is a prime field, uses rational reconstruction to try to find a lift of this element to the rational numbers.

sage: k = GF(97)
sage: a = k(RationalField()('2/3'))
sage: a
33
sage: a.rational_reconstruction()
2/3

trace( self)

Returns the trace of this element.

sage: k = GF(3**3); a = k.gen()
sage: b = a**2 + 2
sage: b.charpoly()
x^3 + x^2 + 2
sage: b.trace()
2
sage: b.norm()
2

Special Functions: __abs__,$  $ __add__,$  $ __cmp__,$  $ __div__,$  $ __float__,$  $ __int__,$  $ __invert__,$  $ __long__,$  $ __mul__,$  $ __neg__,$  $ __pos__,$  $ __rdiv__,$  $ __repr__,$  $ __sub__,$  $ _FiniteFieldElement__compat,$  $ _gap_init_,$  $ _integer_,$  $ _latex_,$  $ _pari_,$  $ _pari_init_

__cmp__( self, other)

Compare an element of a finite field with other. If other is not an element of a finite field, an attempt is made to coerce it so it is one.

sage: k = GF(3**3); a = k.gen()
sage: a == 1
False
sage: a**0 == 1
True
sage: a == a
True
sage: a < a**2
True
sage: a > a**2
False

__invert__( self)

sage: k = GF(9); a = k.gen()
sage: ~a
a + 2
sage: (a+1)*a
2*a + 1

_gap_init_( self)

Supports returning corresponding GAP object. This can be slow since non-prime GAP finite field elements are represented as powers of a generator for the multiplicative group, so the discrete log problem must be solved.

oteThe order of the parent field must be $ \leq 65536$ .

sage: F = GF(8)
sage: a = F.multiplicative_generator()
sage: gap(a)
Z(2^3)
sage: b = F.multiplicative_generator()
sage: a = b^3
sage: gap(a)
Z(2^3)^3
sage: gap(a^3)
Z(2^3)^2

You can specify the instance of the Gap interpreter that is used:

sage: F = GF(next_prime(200)^2)
sage: a = F.multiplicative_generator ()
sage: a._gap_ (gap)  
Z(211^2)
sage: (a^20)._gap_(gap)
Z(211^2)^20

Gap only supports relatively small finite fields.

sage: F = GF(next_prime(1000)^2)
sage: a = F.multiplicative_generator ()
sage: gap(a)
Traceback (most recent call last):
...
TypeError: order (=1018081) must be at most 65536.

_latex_( self)

sage: print latex(Set(GF(9,'z')))
\left\{2z + 2, 2z + 1, 2z, 1, 0, 2, z, z + 1, z + 2
ight\}

_pari_( self)

Return PARI object corresponding to this finite field element.

sage: k = GF(3**3)
sage: a = k.gen()
sage: b = a**2 + 2*a + 1
sage: b._pari_()
Mod(Mod(1, 3)*a^2 + Mod(2, 3)*a + Mod(1, 3), Mod(1, 3)*a^3 + Mod(2, 3)*a +
Mod(1, 3))

Looking at the PARI representation of a finite field element, it's no wonder people find PARI difficult to work with directly. Compare our representation:

sage: b
a^2 + 2*a + 1
sage: b.parent()
Finite Field in a of size 3^3

See About this document... for information on suggesting changes.