An Improvement of the Cipolla-Lehmer Type Algorithms

2015/01/16 by Namhun Koo, Koo, Namhun, Gook Hwa Cho +4
Computer Science · Engineering · Mathematics · #11T06 #11Y16 #68W40 #Coding theory and cryptography #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1501.04036

openalex publication_date 2015/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let F_q be a finite field with q elements with prime power q and let r>1 be an integer with q≡ 1 \pmodr. In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams, and subsequently improved by K. S. Williams and K. Hardy. For a given r-th power residue c in F_q where r is an odd prime, the algorithm of H. C. Williams determines a solution of X^r=c in O(r³log q) multiplications in F_q, and the algorithm of K. S. Williams and K. Hardy finds a solution in O(r⁴+r²log q) multiplications in F_q. Our refinement finds a solution in O(r³+r²log q) multiplications in F_q. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SAGE shows a substantial speed-up compared with the existing algorithms.

Related

• Taking Roots over High Extensions of Finite Fields
• Improvements to the number field sieve for non-prime finite fields
• Multiplication in finite fields with Chudnovsky-type algorithms on the projective line
• A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the 2^r p^s-th Cyclotomic Field
• Finding Primitive Elements in Finite Fields of Small Characteristic