Taking cube roots in \(\mathbb Z_{m}\)
type: Item
instance of: scholarly article
title: Taking cube roots in \(\mathbb Z_{m}\)
zbMATH Open document ID: 1027.11094
DOI: 10.1016/S0893-9659(02)00031-9
author: Carles Padró
author: Germán Sáez
published in: Applied Mathematics Letters
publication date: 2002-09-03T00:00:00Z
review text: The authors investigate methods to compute third roots modulo an integer \(m\). They assume the factorization of \(m\) to be known and thereby reduce the problem to computing third roots modulo a prime \(p\), where the case \(p\equiv 1 \bmod 3\) is the interesting one. The algorithms involve random choices in a given set, therefore, the running times are probabilistic. They provide two generalizations of Peralta's algorithm [\textit{R. Peralta}, IEEE Trans. Inf. Theory 32, 846-847 (1986; Zbl 0658.68043)]. For a cubic residue \(a\) they work in the ring \(\mathbb{Z}_p[x]/(x^3-a)\) and obtain \(\sqrt[3]{a}\) on the cost of computing \(z^{(p-1)/3)}, z\in R\) chosen randomly and one inversion if the result is appropriate. If \(q\) is small in \(p=3^eq+1\) they derive a faster variant. Both have a running time of \(O(\log^3 p)\). The second algorithm extends the Tonelli-Shanks method [see \textit{D. Shanks}, Proc. 2nd Manit. Conf. Numer. Math., Winnipeg 1972, 51-70 (1973; Zbl 0307.10015)]. The algorithm uses properties of the 3-Sylow subgroup of \(\mathbb{Z}_p^*\) and has a running time of \(O(\log^4 p)\).
reviewed by: Tanja Lange
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11-04
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1794935
zbMATH Keywords: cube root
zbMATH Keywords: Peralta algorithm
zbMATH Keywords: Tonelli-Shanks algorithm
MaRDI profile type: Publication
cites work: Q3139838
cites work: A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
cites work: Q5617656
cites work: The Lattice Point Covering Theorem for Rectangles
full work available at URL: s0893-9659(02)00031-9
OpenAlex ID: W1969847147
description: scientific article; zbMATH DE number 1794935