Formulas for cube roots in F-3(m) using shifted polynomial basis

Abstract

Evaluation of cube roots in characteristic three finite fields is required for Tate (or modified Tate) pairing computation. The Hamming weight of x(1/3) means that the number of nonzero coefficients in the polynomial representation of x(1/3) in F-3(m) = F-3[x]/(f), where f is an element of F-3[x] is an irreducible polynomial. The Hamming weight of x(1/3) determines the efficiency of cube roots computation for characteristic three finite fields. Ahmadi et al. found the Hamming weight of x(1/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 x(1/3) and x(2/3). Moreover, we provide the suitable SPB that eliminates modular reduction process in cube roots computation. (c) 2014 Elsevier B.V. All rights reserved.