Formulas for cube roots in F3m using shifted polynomial basis

Evaluation of cube roots in characteristic three finite fields is required for Tate (or modified Tate) pairing computation. The Hamming weight of x1/3 means that the number of nonzero coefficients in the polynomial representation of x1/3 in F3m=F3[x]/(f), where f∈F3[x] is an irreducible polynomial. The Hamming weight of x1/3 determines the efficiency of cube roots computation for characteristic three finite fields. Ahmadi et al. found the Hamming weight of x1/3 using polynomial basis [4]. In this paper, we observe that shifted polynomial basis (SPB), a variation of polynomial basis, can reduce Hamming weights of x1/3 and x2/3. Moreover, we provide the suitable SPB that eliminates modular reduction process in cube roots computation.