Re: Finite fields in Axiom: a few questions

--Copyright The Numerical Algorithms Group Limited 1994.
-- finite field demonstrations
-- prime field
-- get a prime
p:=4817
-- construct field
F:=PrimeField p
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)

-- end of common finite field demonstration
-- finite field with polynomail basis
-- get a small prime
p:=7
P:=PrimeField p
-- get a small extension degree
d:=6
-- get a irreducible polynomial
f:=createIrreduciblePoly(d)$FFPOLY(P)
-- construct field
F:=FFP(P,f)
-- this field is the same as constructed by F:=FFX(P,d) or F:=FF(p,d
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- finite field with normal basis
-- get a normal Polynomial
f:=createNormalPoly(d)$FFPOLY(P)
-- build field
F:=FFNBP(P,f)
-- this field is the same as constructed by F:=FFNBX(P,d) or F:=FFNB(p,d
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- finite field represented as cyclic group
-- because a Zech logarithm table of half the field size is kept in
-- memory during the computations, the size of the field should not be
-- to big.
-- get a small prime
p:=5
P:=PrimeField p
-- get a small extension degree
d:=4
-- get a primitive polynomial
f:=createPrimitivePoly(d)$FFPOLY(P)
-- construct field
F:=FFCGP(P,f)
-- this field is the same as constructed by F:=FFCGX(P,d) or F:=FFCG(p,d
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- polynomial extension of a polynomial extension
-- get a small prime, choose 2 or 3
p:=3
P:=PrimeField p
-- get two small extension degrees
d1:=2
d2:=3
-- get irreducible polynomial of degree d1 over P
f1:=createIrreduciblePoly(d1)$FFPOLY(P)
F1:=FFP(P,f1)
-- get irreducible polynomial of degree d2 over F1
f2:=createIrreduciblePoly(d2)$FFPOLY(F1)
-- construct field
F:=FFP(F1,f2)
-- this field is the same as constructed by F:=FFX(F1,d2)
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
-- end of common finite field demonstration




-- polynomial extension of a normal extension
-- get normal polynomial of degree d1 over P
f1:=createNormalPoly(d1)$FFPOLY(P)
F1:=FFNBP(P,f1)
-- get irreducible polynomial of degree d2 over F1
f2:=createIrreduciblePoly(d2)$FFPOLY(F1)
-- construct field
F:=FFP(F1,f2)
-- this field is the same as constructed by F:=FFX(F1,d2)
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
-- end of common finite field demonstration




-- polynomial extension of a cyclic extension
-- get primitive polynomial of degree d1 over P
f1:=createPrimitivePoly(d1)$FFPOLY(P)
F1:=FFCGP(P,f1)
-- get irreducible polynomial of degree d2 over F1
f2:=createIrreduciblePoly(d2)$FFPOLY(F1)
-- construct field
F:=FFP(F1,f2)
-- this field is the same as constructed by F:=FFX(F1,d2)
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- normal extension of a polynomial extension
-- get a small prime
-- get a irreducible polynomial of degree d1 over P
f1:=createIrreduciblePoly(d1)$FFPOLY(P)
F1:=FFP(P,f1)
-- get a normal polynomial of degree d2 over F1
f2:=createNormalPoly(d2)$FFPOLY(F1)
-- construct field
F:=FFNBP(F1,f2)
-- this field is the same as constructed by F:=FFX(F1,d2)
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- normal extension of a normal extension
-- get a normal polynomial of degree d1 over P
f1:=createNormalPoly(d1)$FFPOLY(P)
F1:=FFNBP(P,f1)
-- get a normal polynomial of degree d2 over F1
f2:=createNormalPoly(d2)$FFPOLY(F1)
-- construct field
F:=FFNBP(F1,f2)
-- this field is the same as constructed by F:=FFX(F1,d2)
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- normal extension of a cyclic extension
-- get primitive polynomial of degree d1 over P
f1:=createPrimitivePoly(d1)$FFPOLY(P)
F1:=FFCGP(P,f1)
-- get a normal polynomial of degree d2 over F1
f2:=createNormalPoly(d2)$FFPOLY(F1)
-- construct field
F:=FFNBP(F1,f2)
-- this field is the same as constructed by F:=FFX(F1,d2)
-- demonstration of common finite field functions
-- the finite field domain is in variable F
-- take some random elements
size()$F
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
-- simple arithmetic
a+b
a-b
a*b
a/b
a**1234
a**(-1)
g := generator()$F
(definingPolynomial()$F::SUP(F)).g
-- functions concerning the multiplicative cyclic group
order(a)
g:=primitiveElement()$F
discreteLog(a)
-- the next one should equal 0
g**% - a
-- the next may fail
discreteLog(b,a)
-- special finite field functions
extensionDegree()$F
degree(a)
normalElement()$F
definingPolynomial()$F
minimalPolynomial(a)
Frobenius(a)
linearAssociatedOrder(a)
linearAssociatedLog(a)
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)


-- end of common finite field demonstration
-- finite field homomorphisms demonstration
P3:= PF 3
-- create a irreducible, a normal and a primitive polynomial
fi:=createIrreduciblePoly(6)$FFPOLY(P3)
fn:=createNormalPoly(6)$FFPOLY(P3)
fp:=createPrimitivePoly(3)$FFPOLY(P3)
-- coercions between field with the same defining polynomials
F:=FFP(P3,fn)
N:=FFNBP(P3,fn)
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
an:=coerce(a)$FFHOM(F,P3,N)
bn:=coerce(b)$FFHOM(F,P3,N)
cn := an*bn
coerce(cn)$FFHOM(F,P3,N)
-- should be the same as
c:=a*b
-- coercion between fields with different extension polynomials
F:=FFP(P3,fi)
N:=FFNBP(P3,fn)
a:=index(size()$F quo 3)$F
b:=index(size()$F quo 7)$F
an:=coerce(a)$FFHOM(F,P3,N)
bn:=coerce(b)$FFHOM(F,P3,N)
cn := an*bn
coerce(cn)$FFHOM(F,P3,N)
-- should be the same as
c:=a*b
-- coercion between fields of different extension degree
C:=FFCGP(P3,fp)
N:=FFNBP(P3,fn)
a:=index(size()$C quo 3)$C
b:=index(size()$C quo 7)$C
an:=coerce(a)$FFHOM(C,P3,N)
bn:=coerce(b)$FFHOM(C,P3,N)
cn := an+bn
coerce(cn)$FFHOM(C,P3,N)
-- should be the same as
c:=a+b
-- comparison of computation times for arithmetic operations
f:=createPrimitiveNormalPoly(5)$FFPOLY(P3)
FP:=FFP(P3,f)
Fc:=FFCGP(P3,f)  -- FC is a domain abbreviation
FN:=FFNBP(P3,f)
ap:=index(size()$FP quo 3)$FP
ac:=coerce(ap)$FFHOM(Fc,P3,FP)
an:=coerce(ap)$FFHOM(FN,P3,FP)
bp:=index(size()$FP quo 7)$FP
bc:=coerce(bp)$FFHOM(Fc,P3,FP)
bn:=coerce(bp)$FFHOM(FN,P3,FP)
-- the next are to initialize the fields
ac+bc
an*bn
-- now we can compare
)set message time on
-- addition
ap+bp
an+bn
ac+bc
-- multiplication
ap*bp
an*bn
ac*bc
-- discrete logarithms
discreteLog(ap)
discreteLog(an)
discreteLog(ac)
-- exponentiation
ap**1234567
an**1234567
ac**1234567
-- computations between elements of field of different representation
ap+bc
an+bc
an+bp