A refinement of Müller's cube root algorithm
type: Item
instance of: scholarly article
title: A refinement of Müller's cube root algorithm
zbMATH Open document ID: 1473.11217
author: Gook Hwa Cho
author: Soonhak Kwon
author: Hyang-Sook Lee
published in: Finite Fields and their Applications
publication date: 2021-02-18T00:00:00Z
review text: For a prime number \(p\), finding cube roots in the finite field \(\mathbb{F}_p\) has several applications in computational number theory. For instance, pairing based cryptosystems (see [\textit{D. Boneh} and \textit{M. Franklin}, Lect. Notes Comput. Sci. 2139, 213--229 (2001; Zbl 1002.94023)] and [\textit{I. Duursma} and \textit{H.-S. Lee}, Lect. Notes Comput. Sci. 2894, 111--123 (2003; Zbl 1189.11056)]) using elliptic and hyperelliptic curves requires basic arithmetic operations including cube root computations. Two standard algorithms for cube root extraction in finite fields are available; Adleman-Manders-Miller (AMM) algorithm which is a generalization of the Tonelli-Shanks square root algorithm, and the Cipolla-Lehmer algorithm. The complexity of the AMM algorithm is \(O(\nu_3(p-1)(\log p)^3)\) bit additions, where \(\nu_3(p-1)\) is the largest nonnegative integer \(e\) such that \(3^e\) divides \(p-1\). If \(\nu_3(p-1) \approx \log p\), we get the worst time complexity \(O((\log p)^4)\). However, the complexity of the Cipolla-Lehmer algorithm is \(O((\log p)^3)\), and it does not depend on \((\nu_3(p-1)\). It follows that, compared with the Cipolla-Lehmer algorithm, the AMM algorithm becomes inefficient for primes \(p\) with large \((\nu_3(p-1)\). \textit{H. C. Williams} [in: Proc. 3rd Southeast. Conf. Combinat., Graph Theory, Computing, Florida Atlantic Univ., Boca Raton. 451--462 (1972; Zbl 0265.10001)] gave a \(q^{\mathrm{th}}\) root algorithm, requiring \(22 \log p\) multiplications. A refinement of this algorithm was given in [\textit{K. S. Williams} and \textit{K. Hardy}, Math. Comput. 61, No. 203, 475--483 (1993; Zbl 0782.11040)] by Williams-Hardy. This algorithm requires \(14.5 \log p\) multiplications. \textit{S. Müller} [Fields Inst. Commun. 41, 293--304 (2004; Zbl 1089.11069)] gave a fast algorithm which needs only \(8.5 \log p\) multiplications. In this paper, the authors present an algorith (an improvement of Müller's algorithm) which needs \(7.5…
reviewed by: Othman Echi
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7312696
zbMATH Keywords: finite field
zbMATH Keywords: cube root
zbMATH Keywords: linear recurrence relation
zbMATH Keywords: Cipolla-Lehmer algorithm
MaRDI profile type: Publication
full work available at URL: j.ffa.2020.101708
OpenAlex ID: W3040926342
cites work: Q4783728
cites work: New cube root algorithm based on the third order linear recurrence relations in finite fields
cites work: Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers
cites work: Advances in Cryptology - ASIACRYPT 2003
cites work: Public-key cryptosystems based on cubic finite field extensions
cites work: Q5617656
cites work: Q4664853
cites work: Q4063214
cites work: Q5682381
cites work: A Refinement of H. C. Williams' qth Root Algorithm
DOI: 10.1016/J.FFA.2020.101708
description: scientific article; zbMATH DE number 7312696