Elements of Finite Fields

EXAMPLES:

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
class sage.rings.finite_field_element.FiniteField_ext_pariElement(parent, value, check=True)

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.

EXAMPLES:

sage: K = FiniteField(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__compat(other)
__abs__()
__cmp__(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.

EXAMPLES:

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
__copy__()

Return a copy of this element.

EXAMPLES:

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: copy(a)
2
sage: b = copy(a)
sage: a == b
True
sage: a is b
False
sage: a is a
True
__float__()
__hash__()
__init__(parent, value, check=True)

Create element of a finite field.

EXAMPLES:

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
__int__()
__invert__()

EXAMPLES:

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
__long__()
__neg__()
__pos__()
__weakref__
list of weak references to the object (if defined)
_add_(right)
_div_(right)
_gap_init_()

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.

Note

The order of the parent field must be \leq 65536.

EXAMPLES:

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)
...
TypeError: order must be at most 65536
_integer_(ZZ=None)
_magma_init_(magma)

Return a string representation of self that Magma can understand.

EXAMPLES:

sage: GF(7)(3)._magma_init_(magma)                 # optional - magma
'GF(7)!3'
_mul_(right)
_pari_(var=None)

Return PARI object corresponding to this finite field element.

EXAMPLES:

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
_pari_init_()
_repr_()
_sub_(right)
is_square()

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

EXAMPLES:

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()

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

EXAMPLES:

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(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.

EXAMPLES:

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

AUTHORS:

  • David Joyner and William Stein (2005-11)
multiplicative_order()

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

EXAMPLES:

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(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 an nth 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 nth 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).

Warning

The ‘extend’ option is not implemented (yet).

AUTHORS:

  • David Roe (2007-10-3)

EXAMPLES:

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)
...
ValueError: no nth root
sage: b.nth_root(4, all=True)
[]
polynomial()

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

EXAMPLES:

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()

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

EXAMPLES:

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(extend=False, all=False)

See self.square_root().

INPUT:

  • extend - ignored
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: 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()
...
ValueError: must be a perfect square.
sage.rings.finite_field_element.is_FiniteFieldElement(x)

Returns if x is a finite field element.

EXAMPLE:

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

Previous topic

Finite Fields

Next topic

Fixed and Arbitrary Precision Numerical Fields

This Page