finite_field_ntl_gf2e.py

from sage.rings.finite_rings.finite_field_base import FiniteField
from sage.libs.pari.all import pari
from finite_field_ext_pari import FiniteField_ext_pari
from sage.rings.integer_ring import ZZ
from sage.rings.integer import Integer
from sage.rings.finite_rings.integer_mod_ring import IntegerModRing_generic

def late_import():
    """
    Imports various modules after startup.

    EXAMPLES::

       sage: sage.rings.finite_rings.finite_field_ntl_gf2e.late_import()
       sage: sage.rings.finite_rings.finite_field_ntl_gf2e.GF2 is None # indirect doctest
       False
    """
    if globals().has_key("GF2"):
        return
    global ResidueField_generic, is_FiniteField, exists_conway_polynomial, conway_polynomial, Cache_ntl_gf2e, GF, GF2, is_Polynomial
    import sage.rings.residue_field
    ResidueField_generic = sage.rings.residue_field.ResidueField_generic

    import sage.rings.finite_rings.finite_field_base
    is_FiniteField = sage.rings.finite_rings.finite_field_base.is_FiniteField

    import sage.rings.finite_rings.constructor
    exists_conway_polynomial = sage.rings.finite_rings.constructor.exists_conway_polynomial
    conway_polynomial = sage.rings.finite_rings.constructor.conway_polynomial

    import sage.rings.finite_rings.constructor
    exists_conway_polynomial = sage.rings.finite_rings.constructor.exists_conway_polynomial

    import sage.rings.finite_rings.element_ntl_gf2e
    Cache_ntl_gf2e = sage.rings.finite_rings.element_ntl_gf2e.Cache_ntl_gf2e

    import sage.rings.finite_rings.constructor
    GF = sage.rings.finite_rings.constructor.GF
    GF2 = GF(2)

    import sage.rings.polynomial.polynomial_element
    is_Polynomial = sage.rings.polynomial.polynomial_element.is_Polynomial

class FiniteField_ntl_gf2e(FiniteField):
    def __init__(self, q, names="a",  modulus=None, repr="poly"):
        """
        Finite Field for characteristic 2 and order >= 2.

        INPUT:
            q       -- 2^n (must be 2 power)
            names   -- variable used for poly_repr (default: 'a')
            modulus -- you may provide a polynomial to use for reduction or
                     a string:
                     'conway': force the use of a Conway polynomial, will
                     raise a RuntimeError if none is found in the database;
                     'minimal_weight': use a minimal weight polynomial, should
                     result in faster arithmetic;
                     'random': use a random irreducible polynomial.
                     'default':a Conway polynomial is used if found. Otherwise
                     a sparse polynomial is used.
            repr  -- controls the way elements are printed to the user:
                     (default: 'poly')
                     'poly': polynomial representation

        OUTPUT:
            Finite field with characteristic 2 and cardinality 2^n.

        EXAMPLES::

            sage: k.<a> = GF(2^16)
            sage: type(k)
            <class 'sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e_with_category'>
            sage: k.<a> = GF(2^1024)
            sage: k.modulus()
            x^1024 + x^19 + x^6 + x + 1
            sage: set_random_seed(0)
            sage: k.<a> = GF(2^17, modulus='random')
            sage: k.modulus()
            x^17 + x^16 + x^15 + x^10 + x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
            sage: k.modulus().is_irreducible()
            True
            sage: k.<a> = GF(2^211, modulus='minimal_weight')
            sage: k.modulus()
            x^211 + x^11 + x^10 + x^8 + 1
            sage: k.<a> = GF(2^211, modulus='conway')
            sage: k.modulus()
            x^211 + x^9 + x^6 + x^5 + x^3 + x + 1
            sage: k.<a> = GF(2^411, modulus='conway')
            Traceback (most recent call last):
            ...
            RuntimeError: requested conway polynomial not in database.

        TESTS::

            sage: k.<a> = GF(2^100, modulus='strangeinput')
            Traceback (most recent call last):
            ...
            ValueError: Modulus parameter not understood
            sage: k.<a> = GF(2^20) ; type(k)
            <class 'sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e_with_category'>
            sage: loads(dumps(k)) is k
            True
            sage: k1.<a> = GF(2^16)
            sage: k2.<a> = GF(2^17)
            sage: k1 == k2
            False
            sage: k3 = k1._finite_field_ext_pari_()
            sage: k1 == k3
            False
        """
        late_import()
        q = Integer(q)
        if q < 2:
            raise ValueError("q must be a 2-power")
        k = q.exact_log(2)
        if q != 1 << k:
            raise ValueError("q must be a 2-power")
        p = Integer(2)
        FiniteField.__init__(self, GF(p), names, normalize=True)

        self._kwargs = {'repr':repr}
        self._is_conway = False

        if modulus is None or modulus == 'default':
            if exists_conway_polynomial(p, k):
                modulus = "conway"
            else:
                modulus = "minimal_weight"
        if modulus == "conway":
            modulus = conway_polynomial(p, k)
            self._is_conway = True
        if is_Polynomial(modulus):
            modulus = modulus.list()
        self._cache = Cache_ntl_gf2e(self, k, modulus)
        self._polynomial = {}

    def characteristic(self):
        """
        Return 2.

        EXAMPLES::

            sage: k.<a> = GF(2^16,modulus='random')
            sage: k.characteristic()
            2
        """
        return Integer(2)

    def order(self):
        """
        Return the cardinality of this field.

        EXAMPLES::

            sage: k.<a> = GF(2^64)
            sage: k.order()
            18446744073709551616
        """
        return self._cache.order()

    def degree(self):
        r"""
        If this field has cardinality `2^n` this method returns `n`.

        EXAMPLES::

            sage: k.<a> = GF(2^64)
            sage: k.degree()
            64
        """
        return self._cache.degree()

    def is_atomic_repr(self):
        """
        Return whether elements of self are printed using an atomic
        representation.

        EXAMPLES::

            sage: k.<a> = GF(2^64)
            sage: k.is_atomic_repr()
            False
            sage: P.<x> = PolynomialRing(k)
            sage: (a+1)*x # indirect doctest
            (a + 1)*x
        """
        return False

    def _element_constructor_(self, e):
        """
        Coerces several data types to self.

        INPUT:
            e -- data to coerce

        EXAMPLES::

            sage: k.<a> = GF(2^20)
            sage: k(1) # indirect doctest
            1
            sage: k(int(2))
            0

            sage: k('a+1')
            a + 1
            sage: k('b+1')
            Traceback (most recent call last):
            ...
            NameError: name 'b' is not defined

            sage: R.<x>=GF(2)[]
            sage: k(1+x+x^10+x^55)
            a^19 + a^17 + a^16 + a^15 + a^12 + a^11 + a^8 + a^6 + a^4 + a^2 + 1

            sage: V = k.vector_space()
            sage: v = V.random_element(); v
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1)
            sage: k(v)
            a^19 + a^15 + a^14 + a^13 + a^11 + a^10 + a^9 + a^6 + a^5 + a^4 + 1
            sage: vector(k(v)) == v
            True

            sage: k(pari('Mod(1,2)*a^20'))
            a^10 + a^9 + a^7 + a^6 + a^5 + a^4 + a + 1
        """
        return self._cache.import_data(e)

    def _coerce_map_from_(self, R):
        """
        Coercion accepts elements of self.parent(), ints, and prime subfield elements.

        EXAMPLES::

            sage: k.<a> = GF(2^8)
            sage: a + int(1) # indirect doctest
            a + 1
            sage: a + 1
            a + 1
            sage: a + GF(2)(1)
            a + 1
        """
        if R is int or R is long or R is ZZ:
            return True
        if is_FiniteField(R):
            if R is self:
                return True
            if isinstance(R, ResidueField_generic):
                return False
            if isinstance(R, IntegerModRing_generic) and R.characteristic() % 2 == 0:
                return True
            if R.characteristic() == 2:
                if R.degree() == 1:
                    return True
                elif self.degree() % R.degree() == 0:
                    # This is where we *would* do coercion from one nontrivial finite field to another...
                    raise NotImplementedError

    def gen(self, ignored=None):
        r"""
        Return a generator of self.

        EXAMPLES::

            sage: k.<a> = GF(2^19)
            sage: k.gen() == a
            True
            sage: a
            a
        """
        return self._cache._gen

    def prime_subfield(self):
        r"""
        Return the prime subfield `\FF_p` of self if self is `\FF_{p^n}`.

        EXAMPLES::

            sage: F.<a> = GF(2^16)
            sage: F.prime_subfield()
            Finite Field of size 2
        """
        return GF2

    def fetch_int(self, number):
        r"""
        Given an integer ``n < self.cardinality()`` with base `2`
        representation `a_0 + 2\cdot a_1 + \cdots 2^k a_k`, returns
        `a_0 + a_1 \cdot x + \cdots a_k x^k`, where `x` is the
        generator of this finite field.

        INPUT:

        - number -- an integer

        EXAMPLES::

            sage: k.<a> = GF(2^48)
            sage: k.fetch_int(2^43 + 2^15 + 1)
            a^43 + a^15 + 1
            sage: k.fetch_int(33793)
            a^15 + a^10 + 1
            sage: 33793.digits(2) # little endian
            [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
        """
        return self._cache.fetch_int(number)

    def polynomial(self, name=None):
        """
        Return the defining polynomial of this field as an element of
        self.polynomial_ring().

        This is the same as the characteristic polynomial of the
        generator of self.

        INPUT:
            name -- optional variable name

        EXAMPLES::

            sage: k.<a> = GF(2^20)
            sage: k.polynomial()
            a^20 + a^10 + a^9 + a^7 + a^6 + a^5 + a^4 + a + 1
            sage: k.polynomial('FOO')
            FOO^20 + FOO^10 + FOO^9 + FOO^7 + FOO^6 + FOO^5 + FOO^4 + FOO + 1
            sage: a^20
            a^10 + a^9 + a^7 + a^6 + a^5 + a^4 + a + 1

        """
        try:
            return self._polynomial[name]
        except KeyError:
            R = self.polynomial_ring(name)
            f = R(self._cache.polynomial())
            self._polynomial[name] = f
            return f

    def _finite_field_ext_pari_(self):
        """
        Return a FiniteField_ext_pari isomorphic to self with the same
        defining polynomial.

        This method will vanish eventually because that implementation of
        finite fields will be deprecated.

        EXAMPLES::

            sage: k.<a> = GF(2^20)
            sage: kP = k._finite_field_ext_pari_()
            sage: kP
            Finite Field in a of size 2^20
            sage: type(kP)
            <class 'sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari_with_category'>
        """
        f = self.polynomial()
        return FiniteField_ext_pari(self.order(), self.variable_name(), f)

    def __hash__(self):
        """
            sage: k1.<a> = GF(2^16)
            sage: {k1:1} # indirect doctest
            {Finite Field in a of size 2^16: 1}
        """
        try:
            return self._hash
        except AttributeError:
            self._hash = hash((self.characteristic(),self.polynomial(),self.variable_name(),"ntl_gf2e"))
            return self._hash

    def _pari_modulus(self):
        """
        Return PARI object which is equivalent to the
        polynomial/modulus of self.

        EXAMPLES::

            sage: k1.<a> = GF(2^16)
            sage: k1._pari_modulus()
            Mod(1, 2)*a^16 + Mod(1, 2)*a^5 + Mod(1, 2)*a^3 + Mod(1, 2)*a^2 + Mod(1, 2)
        """
        f = pari(str(self.modulus()))
        return f.subst('x', 'a') * pari("Mod(1,%s)"%self.characteristic())