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

Young In Cho, Nam Su Chang, Seokhie Hong

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)331-337
Number of pages7
JournalInformation Processing Letters
Issue number6
Publication statusPublished - 2014 Jun


  • Cryptography
  • Cube roots
  • Finite field arithmetic
  • Shifted polynomial basis

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Formulas for cube roots in F 3 m using shifted polynomial basis'. Together they form a unique fingerprint.

Cite this