24.8 Elements of Finite Fields

Module: sage.rings.finite_field_element

Elements of Finite Fields

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

We do some arithmetic involving a bigger field and a Conway polynomial, i.e., we verify compatibility condition.

sage: f = conway_polynomial(2,63)
sage: K.<a> = GF(2**63, name='a', modulus=f)
sage: n = f.degree()
sage: m = 3;
sage: e = (2^n - 1) / (2^m - 1)
sage: c = a^e
sage: conway = conway_polynomial(2,m)
sage: conway(c) == 0
True

Module-level Functions

is_FiniteFieldElement( x)

Returns if x is a finite field element.

sage: is_FiniteFieldElement(1)
    False
sage: is_FiniteFieldElement(IntegerRing())
    False
sage: is_FiniteFieldElement(GF(5)(2))
    True

Class: FiniteField_ext_pariElement

class FiniteField_ext_pariElement
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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: K = FiniteField_ext_pari(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

TESTS:

sage: K.<a> = GF(2^16)
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
FiniteField_ext_pariElement( self, parent, value, [check=True])

Create element of a finite field.

sage: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(9,'a')
sage: a = k(11); a
2
sage: a.parent()
Finite Field in a of size 3^2

Functions: copy,$ \,$ is_square,$ \,$ lift,$ \,$ log,$ \,$ multiplicative_order,$ \,$ nth_root,$ \,$ order,$ \,$ polynomial,$ \,$ rational_reconstruction,$ \,$ sqrt,$ \,$ square_root,$ \,$ vector

copy( self)

Return a copy of this element.

sage: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(3**3,'a')
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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(3**2, 'a')
sage: a = k.gen()
sage: a.is_square()
False
sage: (a**2).is_square()
True
sage: k = FiniteField_ext_pari(2**2,'a')
sage: a = k.gen()
sage: (a**2).is_square()
True
sage: k = FiniteField_ext_pari(17**5,'a'); a = k.gen()
sage: (a**2).is_square()
True
sage: a.is_square()
False

sage: k(0).is_square()
True

lift( self)

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

sage: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
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, base)

Return $ x$ such that $ b^x = a$ , where $ x$ is $ a$ and $ b$ is the base.

Input:

self
- finite field element
b
- finite field element that generates the multiplicative group.

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(3^11).log(F(3))
11
sage: F = GF(113)
sage: F(3^19).log(F(3))
19
sage: F = GF(next_prime(10000))
sage: F(23^997).log(F(23))
997

sage: F = FiniteField(2^10, 'a')
sage: g = F.gen()
sage: b = g; a = g^37
sage: a.log(b)
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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: a = FiniteField_ext_pari(5**3, 'a').0
sage: a.multiplicative_order()
124
sage: a**124
1

nth_root( self, n, [extend=False], [all=False])

Returns an nth root of self.

Input:

n
- integer >= 1 (must fit in C int type)
extend
- bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square is not in the base ring.
all
- bool (default: False); if True, return all square roots of self, instead of just one.

Output: If self has an nth root, returns one (if all == False) or a list of all of them (if all == True). Otherwise, raises a ValueError (if extend = False) or a NotImplementedError (if extend = True).

Author: David Roe (2007-10-3)

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

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 representing 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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(3**2,'a')
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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari 
sage: k = GF(97)
sage: a = k(RationalField()('2/3'))
sage: a
33
sage: a.rational_reconstruction()
2/3

sqrt( self, [extend=False], [all=False])

See self.square_root().

Input:

extend
- ignored

square_root( self, [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 square is not in the base ring.
all
- bool (default: False); if True, return all square roots of self, instead of just one.

sage: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: F = FiniteField_ext_pari(7^2, 'a')
sage: F(2).square_root()
4
sage: F(3).square_root()
5*a + 1
sage: F(3).square_root()**2
3
sage: F(4).square_root()
5
sage: K = FiniteField_ext_pari(7^3, 'alpha')
sage: K(3).square_root()
Traceback (most recent call last):
...
ValueError: must be a perfect square.

vector( self, [reverse=False])

Return a vector in self.parent().vector_space() matching self. The most significant bit is to the right.

Input:

reverse
- reverse the order of the bits from little endian to big endian.

sage: k.<a> = GF(2^16)
sage: e = a^2 + 1
sage: v = e.vector()
sage: v
(1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sage: k(v)
a^2 + 1

sage: k.<a> = GF(3^16)
sage: e = 2*a^2 + 1
sage: v = e.vector()
sage: v
(1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sage: k(v)
2*a^2 + 1

You can also compute the vector in the other order:

sage: e.vector(reverse=True)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1)

Special Functions: __abs__,$ \,$ __cmp__,$ \,$ __float__,$ \,$ __init__,$ \,$ __int__,$ \,$ __invert__,$ \,$ __long__,$ \,$ __neg__,$ \,$ __pos__,$ \,$ _add_,$ \,$ _div_,$ \,$ _FiniteField_ext_pariElement__compat,$ \,$ _gap_init_,$ \,$ _integer_,$ \,$ _magma_init_,$ \,$ _mul_,$ \,$ _pari_,$ \,$ _pari_init_,$ \,$ _repr_,$ \,$ _sub_

__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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari 
sage: a = FiniteField_ext_pari(3**3, 'a').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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: a = FiniteField_ext_pari(9, 'a').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: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: F = FiniteField_ext_pari(8,'a')
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 = FiniteField_ext_pari(next_prime(200)^2, 'a')
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 = FiniteField_ext_pari(next_prime(1000)^2, 'a')
sage: a = F.multiplicative_generator ()
sage: gap._coerce_(a)
Traceback (most recent call last):
...
TypeError: order must be at most 65536

_magma_init_( self)

Return a string representation of self that MAGMA can understand.

_pari_( self, [var=None])

Return PARI object corresponding to this finite field element.

sage: from sage.rings.finite_field_ext_pari import FiniteField_ext_pari
sage: k = FiniteField_ext_pari(3**3, 'a')
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.