We present a method for computing pth roots using a polynomial basis over finite fields Fqm of odd characteristic p, p ≤ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension Fqm of Fq our method requires p - 1 scalar multiplications of elements in Fqm by elements in Fq . In addition, our method requires at most (p-1) [m/p] additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z 1/p , defined as the Hamming weight of z 1/p or wt (z 1/p), is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260-270, 2007) give wt (z1/3) is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ≥ 5, we find wt (z1/p = 1 always.

Additional Metadata
Keywords Finite field arithmetic, Irreducible binomials, Pth roots
Persistent URL dx.doi.org/10.1007/s10623-008-9236-0
Journal Designs, Codes and Cryptography
Panario, D, & Thomson, D. (2009). Efficient pth root computations in finite fields of characteristic p. Designs, Codes and Cryptography, 50(3), 351–358. doi:10.1007/s10623-008-9236-0