The problem of finding roots in F of polynomials in F[x] for F = GF(qm), 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). Generalizing some ideas of Berlekamp and incorporating ideas from existing algorithms, a new method is proposed for finding roots of polynomials over finite extension fields. The proposed technique 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.

Additional Metadata
Persistent URL dx.doi.org/10.1109/18.32139
Journal IEEE Transactions on Information Theory
Citation
Van Oorschot, P, & Vanstone, S.A. (S. A.). (1989). A Geometric Approach to Root Finding in GF(qm). IEEE Transactions on Information Theory, 35(2), 444–453. doi:10.1109/18.32139