axiom-source 20170501-3 / usr / share / axiom-20170501 / src / algebra / IPF.spad

)abbrev domain IPF InnerPrimeField
++ Authors: N.N., J.Grabmeier, A.Scheerhorn
++ Date Created: ?, November 1990, 26.03.1991
++ Date Last Updated: 12 April 1991
++ References:
++ Grab92 Finite Fields in Axiom
++ Lidl83 Finite Field, Encyclopedia of Mathematics and Its Applications
++ Description:
++ InnerPrimeField(p) implements the field with p elements.
++ Note: argument p MUST be a prime (this domain does not check).
++ See \spadtype{PrimeField} for a domain that does check.

InnerPrimeField(p) : SIG == CODE where
  p : PositiveInteger

  I   ==> Integer
  NNI ==> NonNegativeInteger
  PI  ==> PositiveInteger
  TBL ==> Table(PI,NNI)
  R   ==> Record(key:PI,entry:NNI)
  SUP ==> SparseUnivariatePolynomial
  OUT ==> OutputForm

  SIG ==> Join(FiniteFieldCategory,FiniteAlgebraicExtensionField($),_
                ConvertibleTo(Integer))

  CODE ==> IntegerMod p add

    initializeElt:() -> Void
    initializeLog:() -> Void

-- global variables ====================================================

    primitiveElt:PI:=1
    -- for the lookup the primitive Element 
    -- computed by createPrimitiveElement()

    sizeCG  :=(p-1) pretend NonNegativeInteger
    -- the size of the cyclic group

    facOfGroupSize := nil()$(List Record(factor:Integer,exponent:Integer))
    -- the factorization of the cyclic group size

    initlog?:Boolean:=true
    -- gets false after initialization of the logarithm table

    initelt?:Boolean:=true
    -- gets false after initialization of the primitive Element


    discLogTable:Table(PI,TBL):=table()$Table(PI,TBL)
    -- tables indexed by the factors of the size q of the cyclic group
    -- discLogTable.factor is a table of with keys
    -- primitiveElement() ** (i * (q quo factor)) and entries i for
    -- i in 0..n-1, n computed in initialize() in order to use
    -- the minimal size limit 'limit' optimal.

-- functions ===========================================================

    generator() == 1

    -- This uses x**(p-1)=1 (mod p), so x**(q(p-1)+r) = x**r (mod p)
    x:$ ** n:Integer ==
      zero?(n) => 1
      zero?(x) => 0
      r := positiveRemainder(n,p-1)::NNI
      ((x pretend IntegerMod p) **$IntegerMod(p) r) pretend $

    if p <= convert(max()$SingleInteger)@Integer then
      q := p::SingleInteger

      recip x ==
        zero?(y := convert(x)@Integer :: SingleInteger) => "failed"
        invmod(y, q)::Integer::$

    else

      recip x ==
        zero?(y := convert(x)@Integer) => "failed"
        invmod(y, p)::$

    convert(x:$) == x pretend I

    normalElement() == 1

    createNormalElement() == 1

    characteristic() == p

    factorsOfCyclicGroupSize() ==
      p=2 => facOfGroupSize -- this fixes an infinite loop of functions
                            -- calls, problem was that factors factor(1)
                            -- is the empty list
      if empty? facOfGroupSize then initializeElt()
      facOfGroupSize

    representationType() == "prime"

    tableForDiscreteLogarithm(fac) ==
      if initlog? then initializeLog()
      tbl:=search(fac::PI,discLogTable)$Table(PI,TBL)
      tbl case "failed" =>
        error "tableForDiscreteLogarithm: argument must be prime divisor_
 of the order of the multiplicative group"
      tbl pretend TBL

    primitiveElement() ==
      if initelt? then initializeElt()
      index(primitiveElt)

    initializeElt() ==
      facOfGroupSize:=factors(factor(sizeCG)$I)$(Factored I)
      -- get a primitive element
      primitiveElt:=lookup(createPrimitiveElement())
      -- set initialization flag
      initelt? := false
      void$Void

    initializeLog() ==
      if initelt? then initializeElt()
      -- set up tables for discrete logarithm
      limit:Integer:=30
      -- the minimum size for the discrete logarithm table
      for f in facOfGroupSize repeat
        fac:=f.factor
        base:$:=primitiveElement() ** (sizeCG quo fac)
        l:Integer:=length(fac)$Integer
        n:Integer:=0
        if odd?(l)$Integer then n:=shift(fac,-(l quo 2))
                           else n:=shift(1,(l quo 2))
        if n < limit then
          d:=(fac-1) quo limit + 1
          n:=(fac-1) quo d + 1
        tbl:TBL:=table()$TBL
        a:$:=1
        for i in (0::NNI)..(n-1)::NNI repeat
          insert_!([lookup(a),i::NNI]$R,tbl)$TBL
          a:=a*base
        insert_!([fac::PI,copy(tbl)$TBL]_
               $Record(key:PI,entry:TBL),discLogTable)$Table(PI,TBL)
      -- tell user about initialization
      --    print("discrete logarithm table initialized"::OUT)
      -- set initialization flag
      initlog? := false
      void$Void

    degree(x):PI == 1::PositiveInteger

    extensionDegree():PI == 1::PositiveInteger

    inGroundField?(x)  == true

    coordinates(x) == new(1,x)$(Vector $)

    represents(v)  == v.1

    retract(x) == x

    retractIfCan(x) == x

    basis() == new(1,1::$)$(Vector $)

    basis(n:PI) ==
      n = 1 => basis()
      error("basis: argument must divide extension degree")

    definingPolynomial() ==
      monomial(1,1)$(SUP $) - monomial(1,0)$(SUP $)


    minimalPolynomial(x) ==
      monomial(1,1)$(SUP $) - monomial(x,0)$(SUP $)

    charthRoot x == x