On Shanks' Algorithm for Modular Square Roots

zbMATH Open1134.11046arXiv1105.1456MaRDI QIDQ4670089FDOQ4670089

Authors: Jan-Christoph Schlage-Puchta 

Publication date: 15 April 2005

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.

Full work available at URL: https://arxiv.org/abs/1105.1456

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• A complete generalization of Atkin's square root algorithm
• A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem
• Square form factorization
• Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm
• Title not available (Why is that?)
• A Refinement of H. C. Williams' qth Root 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)