scientific article; zbMATH DE number 2154289

From MaRDI portal
Publication:4664853





The author of this paper presents a refinement of Williams' Cipolla-Lehmer procedure of solving congruences of the form \( x^{q} \equiv a\) mod \(p\), where \(a\) is a \(q\)th residue modulo a prime \(p\) (and in particular for the case \(q = 3\)). In his method she utilizes special number-theoretic properties involving the roots of a suitable cubic polynomial. She uses a triple powering ladder which is a natural extension of the simple powering algorithm in \(\mathbb Z_{p}\). The main result of this article is the following theorem: Let \( p\equiv 1 \bmod 3\) be a prime and let \(a\) be a given cubic residue mod \(p\). The proposed algorithm computes a cube root of \(a\) mod \(p\) in two steps: (1) The precomputation finds small \(P\) and \(Q\) for which \( f(x) = x^{3} -Px^{2} + Qx - R\) is irreducible mod \(p\), where \(R = a\). On average , this requires 1.5 evaluations of the generalized cubic Jacobi symbol. (2) Given \(P\) and \(Q\), the body of our algorithm requires 8.5 log \(p\) multiplications on average in \(\mathbb Z_{p}\) only. As H. C. Williams' method, the body of this algorithm requires arithmetic in \(\mathbb Z_{p}\) only and is based on a natural extension of the Cipolla-Lehmer procedure by utilizing some cubic Lucas generalizations. The author provides numerical examples for which the proposed algorithm is much more efficient than the Tonelli-Shanks variant that is usually applied in this context. The author claims that extending the proposed algorithm for finding \(q\)th roots seems to be quite challenging as it would require a much more general theory. For the entire collection see [Zbl 1051.11008].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4664853)