Shanks-Tonelli algorithm


The Shanks-Tonelli algorithm is a procedure for solving a congruenceMathworldPlanetmathPlanetmath of the form x2n(modp), where p is an odd prime and n is a quadratic residueMathworldPlanetmath of p. In other words, it can be used to compute modular square roots.

First find positive integers Q and S such that p-1=2SQ, where Q is odd. Then find a quadratic nonresidue W of p and compute VWQ(modp). Then find an integer n that is the multiplicative inverse of n(modp) (i.e., nn1(modp)).

Compute

RnQ+12(modp)

and find the smallest integer i0 that satisfies

(R2n)2i1(modp)

If i=0, then x=R, and the algorithm stops. Otherwise, compute

RRV2(S-i-1)(modp)

and repeat the procedure for R=R.

Title Shanks-Tonelli algorithm
Canonical name ShanksTonelliAlgorithm
Date of creation 2013-03-22 11:55:16
Last modified on 2013-03-22 11:55:16
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 10
Author mathcam (2727)
Entry type Algorithm
Classification msc 11A07
Classification msc 11Y99