# Question:how do I calculate the pth root of a polynomial over a finite field? (Squarefree Factorization Algo)

## Question:how do I calculate the pth root of a polynomial over a finite field? (Squarefree Factorization Algo)

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!

﻿