Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Finite fields implemented via PARI's FFELT type
AUTHORS:
- Peter Bruin (June 2013): initial version, based on finite_field_ext_pari.py by William Stein et al. """ from __future__ import absolute_import
#***************************************************************************** # Copyright (C) 2013 Peter Bruin <peter.bruin@math.uzh.ch> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from .element_pari_ffelt import FiniteFieldElement_pari_ffelt from .finite_field_base import FiniteField from .finite_field_constructor import GF
class FiniteField_pari_ffelt(FiniteField): """ Finite fields whose cardinality is a prime power (not a prime), implemented using PARI's ``FFELT`` type.
INPUT:
- ``p`` -- prime number
- ``modulus`` -- an irreducible polynomial of degree at least 2 over the field of `p` elements
- ``name`` -- string: name of the distinguished generator (default: variable name of ``modulus``)
OUTPUT:
A finite field of order `q = p^n`, generated by a distinguished element with minimal polynomial ``modulus``. Elements are represented as polynomials in ``name`` of degree less than `n`.
.. NOTE::
Direct construction of :class:`FiniteField_pari_ffelt` objects requires specifying a characteristic and a modulus. To construct a finite field by specifying a cardinality and an algorithm for finding an irreducible polynomial, use the ``FiniteField`` constructor with ``impl='pari_ffelt'``.
EXAMPLES:
Some computations with a finite field of order 9::
sage: k = FiniteField(9, 'a', impl='pari_ffelt') sage: k Finite Field in a of size 3^2 sage: k.is_field() True sage: k.characteristic() 3 sage: a = k.gen() sage: a a sage: a.parent() Finite Field in a of size 3^2 sage: a.charpoly('x') x^2 + 2*x + 2 sage: [a^i for i in range(8)] [1, a, a + 1, 2*a + 1, 2, 2*a, 2*a + 2, a + 2] sage: TestSuite(k).run()
Next we compute with a finite field of order 16::
sage: k16 = FiniteField(16, 'b', impl='pari_ffelt') sage: z = k16.gen() sage: z b sage: z.charpoly('x') x^4 + x + 1 sage: k16.is_field() True sage: k16.characteristic() 2 sage: z.multiplicative_order() 15
Illustration of dumping and loading::
sage: K = FiniteField(7^10, 'b', impl='pari_ffelt') sage: loads(K.dumps()) == K True
sage: K = FiniteField(10007^10, 'a', impl='pari_ffelt') sage: loads(K.dumps()) == K True """ def __init__(self, p, modulus, name=None): """ Create a finite field of characteristic `p` defined by the polynomial ``modulus``, with distinguished generator called ``name``.
EXAMPLES::
sage: from sage.rings.finite_rings.finite_field_pari_ffelt import FiniteField_pari_ffelt sage: R.<x> = PolynomialRing(GF(3)) sage: k = FiniteField_pari_ffelt(3, x^2 + 2*x + 2, 'a'); k Finite Field in a of size 3^2 """
Element = FiniteFieldElement_pari_ffelt
def __reduce__(self): """ For pickling.
EXAMPLES::
sage: k.<b> = FiniteField(5^20, impl='pari_ffelt') sage: type(k) <class 'sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt_with_category'> sage: k is loads(dumps(k)) True """
def gen(self, n=0): """ Return a generator of ``self`` over its prime field, which is a root of ``self.modulus()``.
INPUT:
- ``n`` -- must be 0
OUTPUT:
An element `a` of ``self`` such that ``self.modulus()(a) == 0``.
.. WARNING::
This generator is not guaranteed to be a generator for the multiplicative group. To obtain the latter, use :meth:`~sage.rings.finite_rings.finite_field_base.FiniteFields.multiplicative_generator()` or use the ``modulus="primitive"`` option when constructing the field.
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(2)) sage: FiniteField(2^4, 'b', impl='pari_ffelt').gen() b sage: k = FiniteField(3^4, 'alpha', impl='pari_ffelt') sage: a = k.gen() sage: a alpha sage: a^4 alpha^3 + 1 """ raise IndexError("only one generator")
def characteristic(self): """ Return the characteristic of ``self``.
EXAMPLES::
sage: F = FiniteField(3^4, 'a', impl='pari_ffelt') sage: F.characteristic() 3 """ # This works since self is not its own prime field.
def degree(self): """ Returns the degree of ``self`` over its prime field.
EXAMPLES::
sage: F = FiniteField(3^20, 'a', impl='pari_ffelt') sage: F.degree() 20 """
def _element_constructor_(self, x): """ Construct an element of ``self``.
INPUT:
- ``x`` -- object
OUTPUT:
A finite field element generated from `x`, if possible.
.. NOTE::
If `x` is a list or an element of the underlying vector space of the finite field, then it is interpreted as the list of coefficients of a polynomial over the prime field, and that polynomial is interpreted as an element of the finite field.
EXAMPLES::
sage: k = FiniteField(3^4, 'a', impl='pari_ffelt') sage: b = k(5) # indirect doctest sage: b.parent() Finite Field in a of size 3^4 sage: a = k.gen() sage: k(a + 2) a + 2
Univariate polynomials coerce into finite fields by evaluating the polynomial at the field's generator::
sage: R.<x> = QQ[] sage: k.<a> = FiniteField(5^2, 'a', impl='pari_ffelt') sage: k(R(2/3)) 4 sage: k(x^2) a + 3
sage: R.<x> = GF(5)[] sage: k(x^3-2*x+1) 2*a + 4
sage: x = polygen(QQ) sage: k(x^25) a
sage: Q.<q> = FiniteField(5^7, 'q', impl='pari_ffelt') sage: L = GF(5) sage: LL.<xx> = L[] sage: Q(xx^2 + 2*xx + 4) q^2 + 2*q + 4
sage: k = FiniteField(3^11, 't', impl='pari_ffelt') sage: k.polynomial() t^11 + 2*t^2 + 1 sage: P = k.polynomial_ring() sage: k(P.0^11) t^2 + 2
An element can be specified by its vector of coordinates with respect to the basis consisting of powers of the generator:
sage: k = FiniteField(3^11, 't', impl='pari_ffelt') sage: V = k.vector_space() sage: V Vector space of dimension 11 over Finite Field of size 3 sage: v = V([0,1,2,0,1,2,0,1,2,0,1]) sage: k(v) t^10 + 2*t^8 + t^7 + 2*t^5 + t^4 + 2*t^2 + t
Multivariate polynomials only coerce if constant::
sage: k = FiniteField(5^2, 'a', impl='pari_ffelt') sage: R = k['x,y,z']; R Multivariate Polynomial Ring in x, y, z over Finite Field in a of size 5^2 sage: k(R(2)) 2 sage: R = QQ['x,y,z'] sage: k(R(1/5)) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
Gap elements can also be coerced into finite fields::
sage: F = FiniteField(2^3, 'a', impl='pari_ffelt') sage: a = F.multiplicative_generator(); a a sage: b = gap(a^3); b Z(2^3)^3 sage: F(b) a + 1 sage: a^3 a + 1
sage: a = GF(13)(gap('0*Z(13)')); a 0 sage: a.parent() Finite Field of size 13
sage: F = FiniteField(2^4, 'a', impl='pari_ffelt') sage: F(gap('Z(16)^3')) a^3 sage: F(gap('Z(16)^2')) a^2
You can also call a finite extension field with a string to produce an element of that field, like this::
sage: k = GF(2^8, 'a') sage: k('a^200') a^4 + a^3 + a^2
This is especially useful for conversion from Singular etc.
TESTS::
sage: k = FiniteField(3^2, 'a', impl='pari_ffelt') sage: a = k(11); a 2 sage: a.parent() Finite Field in a of size 3^2 sage: V = k.vector_space(); v = V((1,2)) sage: k(v) 2*a + 1
We create elements using a list and verify that :trac:`10486` has been fixed::
sage: k = FiniteField(3^11, 't', impl='pari_ffelt') sage: x = k([1,0,2,1]); x t^3 + 2*t^2 + 1 sage: x + x + x 0 sage: pari(x) t^3 + 2*t^2 + 1
If the list is longer than the degree, we just get the result modulo the modulus::
sage: from sage.rings.finite_rings.finite_field_pari_ffelt import FiniteField_pari_ffelt sage: R.<a> = PolynomialRing(GF(5)) sage: k = FiniteField_pari_ffelt(5, a^2 - 2, 't') sage: x = k([0,0,0,1]); x 2*t sage: pari(x) 2*t
When initializing from a list, the elements are first coerced to the prime field (:trac:`11685`)::
sage: k = FiniteField(3^11, 't', impl='pari_ffelt') sage: k([ 0, 1/2 ]) 2*t sage: k([ k(0), k(1) ]) t sage: k([ GF(3)(2), GF(3^5,'u')(1) ]) t + 2 sage: R.<x> = PolynomialRing(k) sage: k([ R(-1), x/x ]) t + 2
Check that zeros are created correctly (:trac:`11685`)::
sage: K = FiniteField(3^11, 't', impl='pari_ffelt'); a = K.0 sage: v = 0; pari(K(v)) 0 sage: v = Mod(0,3); pari(K(v)) 0 sage: v = pari(0); pari(K(v)) 0 sage: v = pari("Mod(0,3)"); pari(K(v)) 0 sage: v = []; pari(K(v)) 0 sage: v = [0]; pari(K(v)) 0 sage: v = [0,0]; pari(K(v)) 0 sage: v = pari("Pol(0)"); pari(K(v)) 0 sage: v = pari("Mod(0, %s)"%K.modulus()); pari(K(v)) 0 sage: v = pari("Mod(Pol(0), %s)"%K.modulus()); pari(K(v)) 0 sage: v = K(1) - K(1); pari(K(v)) 0 sage: v = K([1]) - K([1]); pari(K(v)) 0 sage: v = a - a; pari(K(v)) 0 sage: v = K(1)*0; pari(K(v)) 0 sage: v = K([1])*K([0]); pari(K(v)) 0 sage: v = a*0; pari(K(v)) 0 """ return x else: |