No label defined (Q4664853)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2154289
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2154289 |
Statements
8 April 2005
0 references
Algorithm
0 references
quadratic roots modulo \(p\)
0 references
cubic roots modulo \(p\)
0 references
Bell functions
0 references
Cipolla-Lehmer procedure
0 references
Jacobi symbol
0 references
cubic Lucas generalizations
0 references
Tonelli-Shanks procedure
0 references
triple powering ladder.
0 references
0.8901004195213318
0 references
0.8901004195213318
0 references
0.8851180672645569
0 references
0.8592060208320618
0 references
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].
0 references