On Shanks' Algorithm for Modular Square Roots

zbMATH Open1134.11046arXiv1105.1456MaRDI QIDQ4670089

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

Mathematics Subject Classification ID

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

Related Items (1)

A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)

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)