Taking cube roots in \(\mathbb Z_{m}\) (Q1614110): Difference between revisions

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)\).