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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references