## 15 Reputation

0 years, 308 days

## how do I calculate the pth root of a pol...

Maple

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!

## [Finite-field arithmetic] not working.....

Maple

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?

## No polynom in x??...

Maple

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!!

## residue class ring, how do I define the ...

Maple

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!!

## return vs print, How do I reach the prin...

Maple

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.
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

 Page 1 of 1
﻿