A geometric approach to root finding in GT(qm)

The problem of finding roots in F of polynomials in F [x] for F=GF(q^m), where q is a prime or prime power and m is a positive integer greater than 1 is considered. The problem is analyzed by making use of the finite affine geometry AG(m,q). A new method is proposed for finding roots of polynomials over finite extension fields. It is more efficient than previous algorithms when the degree of the polynomial whose roots are to be found is less than dimension m of the extension field. Implementation of the algorithm can be enhanced in cases in which optimal normal bases for the coefficient field are available