Hello,

I would like to evaluate a funktion f in \F_q[x], where \F_q is a finite field with q=p^k. My algorithm is based on the fast multipoint evaluation algo in J. von zur Gathen/ J. Gerhard Modern Computer Algebra Edition 3. My proc FastEval does the right thing, but I dont know how to reach any of the calculatet values. And I will need all of the values for further procs! I tried it with lists, but (because of the recursive call??) I only get 1 value in the list... Does anyone know how to solve my problem? The return call only stops my proc after the first value has been calculated, that is why i used print.

Please, can anyone help me?

This is my first question asked in mapleprimes.com, so please excuse any mistakes.. Also I dont know how to put the maple stuff in here correctly??

I would be really really happy if anyone can help me...

Kind regards from Germany

Melanie

\sourceon Maple

istZweierpotenz := proc (n::posint) #checks if n=2^k for any k in N

local k, nTest;

k := 0; nTest := 1;

while nTest <= n do

if nTest = n then return true

else nTest := 2*nTest; k := k+1

end if

end do;

return false

end proc;

with(ListTools);

SubProdTree := proc (n::posint, u::(seq(anything)))

local k, j, i, M::(polynom(integer, x)), leftList, rightList, kList;

if istZweierpotenz(n) = true then k := log[2](n);

if nops([u]) = n then

for j to nops([u]) do M[0, j-1] := x-u[j]

end do;

for kList from 0 to k do leftList[0, kList] := [M[0, 2*kList]]; rightList[0, kList] := [M[0, 2*kList+1]]

end do;

for i to k do for j from 0 to 2^(k-i)-1 do M[i, j] := M[i-1, 2*j]*M[i-1, 2*j+1]

end do;

for kList from 0 to 2^(k-i-1)-1 do leftList[i, kList]

:= Flatten([[leftList[i-1, 2*kList]], [rightList[i-1, 2*kList]], M[i, 2*kList]]); rightList[i, kList]

:= Flatten([leftList[i-1, 2*kList+1], rightList[i-1, 2*kList+1], M[i, 2*kList+1]])

end do;

if i = k then kList := 0;

leftList[i, kList] := Flatten([[leftList[i-1, 2*kList]], [rightList[i-1, 2*kList]], M[i, 2*kList]])

end if

end do;

return leftList[k, 0]

else

return false

end if

else return false

end if

end proc;

GoDownTree := proc (f::polynom, n::posint, l::list, p::posint)

local func, prim, k, r0, r1, newLeftList, newRightList, numberPoint, newList;

func := f;

prim := p;

numberPoint := n;

k := log[2](numberPoint);

newList := l;

newLeftList := newList[1 .. numberPoint-1];

newRightList := newList[numberPoint .. 2*numberPoint-2];

if not isprime(prim) then return sprintf("%a ist nicht prim", prim)

end if;

if numberPoint < degree(func) then return false

end if;

if numberPoint = 1 then print(func)

else

r0 := evala(`mod`(Rem(func, newLeftList[-1], x), prim));

r1 := evala(`mod`(Rem(func, newRightList[-1], x), prim));

GoDownTree(r0, (1/2)*numberPoint, newLeftList, prim);

GoDownTree(r1, (1/2)*numberPoint, newRightList, prim)

end if

end proc;

FastEval := proc (f::polynom, n::posint, p::posint, u::(seq(anything))) local l;

l := SubProdTree(n, u);

GoDownTree(f, n, l, p)

end proc;

G := GF(11, 2);

a := G:-extension;

aOut := G:-ConvertOut(a);

alias(alpha = RootOf(aOut));

l := SubProdTree(8, 1, 2, 3, 4, 5, 6, 7, 8);

GoDownTree(x^2+x+1, 8, l, 11);

GF(11, 2)

/ 2 \

\T + 6 T + 7/ mod 11

2

T + 6 T + 7

alpha

[x - 1, x - 2, (x - 1) (x - 2), x - 3, x - 4, (x - 3) (x - 4),

(x - 1) (x - 2) (x - 3) (x - 4), x - 5, x - 6, (x - 5) (x - 6),

x - 7, x - 8, (x - 7) (x - 8), (x - 5) (x - 6) (x - 7) (x - 8),

(x - 1) (x - 2) (x - 3) (x - 4) (x - 5) (x - 6) (x - 7) (x - 8)

]

3

7

2

10

9

10

2

7

FastEval(x^2+x+1, 8, 11, 1, 2, 3, 4, 5, 6, 7, 8);

3

7

2

10

9

10

2

7

\sourceoff