Hello,
I am trying to implement a Squarefree Factorization Algo in Maple. 
For several algorithms (like the one in Victor Shoup- A computational Introduction to Number Theory and Algebra) one is in need of computing the pth root (F_q is the finite field with q=p^k) of a polynomial. I tried stuff like pol^(1/p), root[p](pol), proot(pol,p), but either I get NOROOT as output or just the polynomial with the exponent 1/p, like e.g.

(x^6+(2*tau+1)*x^3+2)^(1/3)

(tau my RootOf for the field extension, F_q with q=3^2)
But that doesnt help me, because I will need a polynomial without any exponent so that i can get the derivate pol'=dpol/dx, and that doenst work if there is any exponent...
cTest := `mod`(root[p](c), p);
cStrich := `mod`(diff(cTest, x), p);
          (x^6+(2*tau+1)*x^3+2)^(1/3)                    
          Error, the modular inverse does not exist

Does anybody know how I can calculate the pth root of a polynomial? (At the moment I am following the Algo that is mentioned on wiki for Squarefree Factorization...)

Or, does anybody know a better Algo for a squarefree Factorization? 

Thanks for any help and any answers!

Ok I am still not further... Lets assume wie have F_q with q=3^2 and the irreducible polynomial T^2+2T+2...
Be tau the alsias(tau=RootOf(T^2+2T+2));
Then I get in Maple the wrong (??) calculation 

(tau+1)(2tau+2)= tau+1 \neq 1, which is supposed to be the right answer: =2tau^2+4tau+2=2(tau^2+2tau+2)-2=0-2=1 because our prime number is 3... WHY does Maple not calculate that stuff correctly??

Another problem:
Be f:= x^2+tau*x;
When I enter Rem(x^q,f,x) mod 3 then Maple returns x, whereas I calculate (tau+1)x...
Where is the mistake?
I build my finite field either via firred := T^2+2*T+2; alias(tau = RootOf(firred))

or 
G := GF(3, 2); a := G:-extension; aOut := G:-ConvertOut(a); alias(tau = RootOf(aOut))

But both times the calculations are not correct... I dont know why? 

Please, can somebody help?

Hello,

I have another problem and maybe someone can help me.
When I enter the code: 

with  alias(tau=RootOf(T^2+2T+2)) ;
then Maple gives me the output false???
Why is it false??
Can someone help me?
How do I tell Maple that for example f:= x^2+tau*x is a Polynom with x=variable, tau= RootOf?
Thank you!!

Hello,

I do know how to define the finite field F_q=GF(p,k). But know I am looking at the residue class ring R:= \F_q[x]/(f) with f an arbitrary polynomial in F_q[x]  of degree(f)>1. And I need all the calculations over R. My f will be reducible, so R wont be a field. Can anyone help me how I tell Maple to do the arithmetic in R? With the right remainder calculation? And with [f]=[0], so that the sesidue class of f is the same as the residue class of 0?

Thank you very much for any help!!

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