/usr/share/axiom-20170501/src/algebra/FFPOLY2.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | )abbrev package FFPOLY2 FiniteFieldPolynomialPackage2
++ Authors: J.Grabmeier, A.Scheerhorn
++ Date Created: 26.03.1991
++ References:
++ Grab92 Finite Fields in Axiom
++ Lidl83 Finite Field, Encyclopedia of Mathematics and Its Applications
++ Description:
++ FiniteFieldPolynomialPackage2(F,GF) exports some functions concerning
++ finite fields, which depend on a finite field GF and an
++ algebraic extension F of GF, for example, a zero of a polynomial
++ over GF in F.
FiniteFieldPolynomialPackage2(F,GF) : SIG == CODE where
F : FieldOfPrimeCharacteristic with
coerce : GF -> F
++ coerce(x) \undocumented{}
lookup : F -> PositiveInteger
++ lookup(x) \undocumented{}
basis : PositiveInteger -> Vector F
++ basis(n) \undocumented{}
Frobenius : F -> F
++ Frobenius(x) \undocumented{}
-- F should be a algebraic extension of the finite field GF, either an
-- algebraic closure of GF or a simple algebraic extension field of GF
GF : FiniteFieldCategory
I ==> Integer
NNI ==> NonNegativeInteger
PI ==> PositiveInteger
SUP ==> SparseUnivariatePolynomial
MM ==> ModMonic(GF,SUP GF)
OUT ==> OutputForm
M ==> Matrix
V ==> Vector
L ==> List
FFPOLY ==> FiniteFieldPolynomialPackage(GF)
SUPF2 ==> SparseUnivariatePolynomialFunctions2(GF,F)
SIG ==> with
rootOfIrreduciblePoly:SUP GF -> F
++ rootOfIrreduciblePoly(f) computes one root of the monic,
++ irreducible polynomial f,
++ which degree must divide the extension degree
++ of F over GF,
++ f splits into linear factors over F.
CODE ==> add
-- we use berlekamps trace algorithm
-- it is not checked whether the polynomial is irreducible over GF]]
rootOfIrreduciblePoly(pf) ==
sizeGF:=size()$GF
-- if the polynomial is of degree one, we're ready
deg:=degree(pf)$(SUP GF)::PI
deg = 0 => error("no roots")
deg = 1 => -coefficient(pf,0)$(SUP GF)::F
p : SUP F := map(coerce,pf)$SUPF2
-- compute qexp, qexp(i) = x **(size()GF ** i) mod p
-- with this list it's easier to compute the gcd(p(x),trace(x))
qexp:=reducedQPowers(pf)$FFPOLY
stillToFactor:=p
-- take linear independent elements, the basis of F over GF
basis:Vector F:=basis(deg)$F
basispointer:I:=1
-- as p is irreducible over GF, 0 can't be a root of p
-- therefore we can use the predicate zero?(root) for indicating
-- whether a root is found
root:=0$F
while zero?(root)$F repeat
beta:F:=basis.basispointer
-- gcd(trace(x)+gf,p(x)) has degree 0,that's why we skip beta=1
if beta = 1$F then
basispointer:=basispointer + 1
beta:= basis.basispointer
basispointer:=basispointer+1
-- compute the polynomial trace(beta * x) mod p(x) using explist
trModp:SUP F:= map(coerce,qexp.0)$SUPF2 * beta
for i in 1..deg-1 repeat
beta:=Frobenius(beta)
trModp:=trModp +$(SUP F) beta *$(SUP F) map(coerce,qexp.i)$SUPF2
-- if it is of degree 0, it doesn't help us finding a root
if degree(trModp)$(SUP F) > 0 then
-- for all elements gf of GF do
for j in 1..sizeGF repeat
-- compute gcd(trace(beta * x) + gf,stillToFactor)
h:=gcd(stillToFactor,trModp +$(SUP F) _
(index(j pretend PI)$GF::F::(SUP F)))$(SUP F)
-- make the gcd polynomial monic
if leadingCoefficient(h)$(SUP F) ^= 1$F then
h:= (inv leadingCoefficient(h)) * h
degh:=degree(h)$(SUP F)
degSTF:=degree(stillToFactor)$(SUP F)
-- if the gcd has degree one we are ready
degh = 1 => root:=-coefficient(h,0)$(SUP F)
-- if the quotient of stillToFactor and the gcd has
-- degree one, we're also ready
degSTF - degh = 1 =>
root:= -coefficient(stillToFactor quo h,0)$(SUP F)
-- otherwise the gcd helps us finding a root, only if its
-- degree is between 2 and degree(stillToFactor)-2
if degh > 1 and degh < degSTF then
2*degh > degSTF => stillToFactor := stillToFactor quo h
stillToFactor := h
root
|