Improvement Of Barreto-Voloch Algorithm For Computing rth Roots Over Finite Fields

2011/10/19 by Zhengjun Cao, Cao, Zhengjun, Fan Xiao +1
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)

paper · pdf · doi:10.48550/arxiv.1110.4801

openalex publication_date 2011/10/19 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

Root extraction is a classical problem in computers algebra. It plays an essential role in cryptosystems based on elliptic curves. In 2006, Barreto and Voloch proposed an algorithm to compute rth roots in F_q^m for certain choices of m and q. If r || q-1 and (m, r)=1, they proved that the complexity of their method is \widetilde\mathcal O(r(log m+loglog q)mlog q) . In this paper, we extend the Barreto-Voloch algorithm to the general case that r || q^m-1, without the restrictions r || q-1 and (m, r)=1 . We also specify the conditions that the Barreto-Voloch algorithm can be preferably applied.

Citations

• Identity-Based Encryption from the Weil Pairing

Related

• On Taking r-th Roots without r-th Nonresidues over Finite Fields and Its Applications
• Taking Roots over High Extensions of Finite Fields
• Adleman-Manders-Miller Root Extraction Method Revisited
• Computing e-th roots in number fields
• Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields