On Shanks' Algorithm for Modular Square Roots

MaRDI QIDQ4670089zbMATH OpenFDO

Authors Jan-Christoph Schlage-Puchta

Publication date 15 April 2005

Full work available at URL https://arxiv.org/abs/1105.1456, https://eudml.org/doc/53938

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Abstract: Let $p$ be a prime number, $p=2^{n}q+1$, where $q$ is odd. D. Shanks described an algorithm to compute square roots $pmodp$ which needs $O(logq+n^2)$ modular multiplications. In this note we describe two modifications of this algorithm. The first needs only $O(logq+n^{3/2})$ modular multiplications, while the second is a parallel algorithm which needs $n$ processors and takes $O(logq+n)$ time.

Recommendations

• scientific article; zbMATH DE number 2086246
• scientific article; zbMATH DE number 1303185
• A complete generalization of Atkin's square root algorithm
• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• Square Roots mod p

Cited in

(9)

• A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem
• A complete generalization of Atkin's square root algorithm
• scientific article; zbMATH DE number 2086246 (Why is no real title available?)
• A Refinement of H. C. Williams' qth Root Algorithm
• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• scientific article; zbMATH DE number 1303185 (Why is no real title available?)
• Square Roots mod p
• Square form factorization
• Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm

This page was built for publication: On Shanks' Algorithm for Modular Square Roots

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