scientific article; zbMATH DE number 2154289
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].
- Taking cube roots in \(\mathbb Z_{m}\)
- A refinement of Müller's cube root algorithm
- New cube root algorithm based on the third order linear recurrence relations in finite fields
- On the Cipolla-Lehmer type algorithms in finite fields
- A solution to the congruence x^3 a p
- A New Algorithm for Long Integer Cube Computation with Some Insight into Higher Powers
- A Refinement of H. C. Williams' qth Root Algorithm
- scientific article; zbMATH DE number 3954156 (Why is no real title available?)
- scientific article; zbMATH DE number 826069 (Why is no real title available?)
- Improving the Pocklington and Padró-Sáez cube root algorithm
- On the computation of r-th roots in finite fields
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)