Formulas for cube roots in \(\mathbb F_{3^m}\) (Q868380)

The paper studies some properties of cube roots in a finite field of characteristic three. The authors argue the interest of characteristic three fields in pairing-based cryptographic protocols and they point out that ``the fastest algorithms known for pairing computations\dots requires the evaluation of cube roots in \(F_{3^m}\)''. Let \(F_{3^m}\) be represented as \(F_3(x)=F_3[X]/(f)\), with \(f(X)\in F_3[X]\) an irreducible trinomial. Expressing the elements of \(F_{3^m}\) in the polynomial basis \(\{1,x,\dots, x^{m-1}\}\), the computation of cube roots reduces to multiplications by \(x^{1/3}, x^{2/3}\). These multiplications would be more efficient if \(x^{1/3}, x^{2/3}\) have low Hamming weight. The paper determines the Hamming weight of \(x^{1/3}\). Let \(f(X)=X^m+aX^k+b\) be the irreducible trinomial. Section 2 deals with the case \(m\not \equiv -k \bmod 3\). Several theorems give the value \(w(x^{1/3})\) in terms of the congruences of \(m\) and \(k\) modulo 3. A similar study is accomplished in Section 3 when \(m\equiv -k \bmod 3\). Theorem 7 shows that in this case \(w(x^{1/3})\in \{(m/d)-2, (m/d)-1, m/d \}\), where \(d=\text{gcd} (m,k)\). The proof of this result is divided in three cases and it is accompanied with eight Tables. A further Table listing \(w(x^{1/3})\) for all irreducible trinomials of degrees \(m\in [2,56]\) is given as an Appendix.