Formulas for cube roots in F 3 ^m 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 F3_m= ^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.