A refinement of Müller's cube root algorithm

Gook Hwa Cho, Soonhak Kwon, Hyang Sook Lee

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Let p be a prime such that p≡1(mod3). Let c be a cubic residue (modp) such that [Formula presented]. In this paper, we present a refinement of Müller's algorithm for computing a cube root of c [11], which also improves Williams' [14,15] Cipolla-Lehmer type algorithms. Under the assumption that a suitable irreducible polynomial of degree 3 is given, Müller gave a cube root algorithm which requires 8.5log⁡p modular multiplications. Our algorithm requires only 7.5log⁡p modular multiplications and is based on the recurrence relations arising from the irreducible polynomial h(x)=x3+ct3x−ct3 for some integer t.

Original languageEnglish
Article number101708
JournalFinite Fields and their Applications
Volume67
DOIs
StatePublished - Oct 2020

Keywords

  • Cipolla-Lehmer algorithm
  • Cube root
  • Finite field
  • Linear recurrence relation

Fingerprint

Dive into the research topics of 'A refinement of Müller's cube root algorithm'. Together they form a unique fingerprint.

Cite this