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
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
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
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
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
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
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
self, base) |
Return
such that
, where
is
and
is the base.
Input:
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)
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
self, n, [extend=False], [all=False]) |
Returns an nth root of self.
Input:
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) []
self) |
Return the additive order of this finite field element.
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
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
self, [extend=False], [all=False]) |
See self.square_root().
Input:
self, [extend=False], [all=False]) |
The square root function.
Input:
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.
self, [reverse=False]) |
Return a vector in self.parent().vector_space() matching self. The most significant bit is to the right.
Input:
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_
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
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
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
.
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
self) |
Return a string representation of self that MAGMA can understand.
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.