In computational number theory, the [[wp:Tonelli–Shanks algorithm|Tonelli–Shanks algorithm]] is a technique for solving for '''x''' in a congruence of the form:
<big>
:: x<sup>2</sup> ≡ n (mod p)
</big>
where '''n''' is an integer which is a quadratic residue (mod p), '''p''' is an odd prime, and '''x,n ∈ F<sub>p</sub>''' where F<sub>p</sub> = {0, 1, ..., p - 1}.

It is used in [https://en.wikipedia.org/wiki/Rabin_cryptosystem cryptography] techniques.


To apply the algorithm, we need the Legendre symbol:

The Legendre symbol '''(a | p)''' denotes the value of a<sup>(p-1)/2</sup> (mod p).
* '''(a | p) ≡ 1''' &nbsp;&nbsp; if '''a''' is a square (mod p)
* '''(a | p) ≡ -1''' &nbsp;&nbsp; if '''a''' is not a square (mod p)
* '''(a | p) ≡ 0''' &nbsp;&nbsp; if '''a''' ≡ 0 (mod p) 


;Algorithm pseudo-code:
<big>
All ≡ are taken to mean (mod p) unless stated otherwise.

* Input: '''p''' an odd prime, and an integer '''n''' .
* Step 0: Check that '''n''' is indeed a square: (n | p) must be ≡ 1 .
* Step 1: By factoring out powers of 2 from p - 1, find '''q''' and '''s''' such that p - 1 = q2<sup>s</sup> with '''q''' odd .
** If p ≡ 3 (mod 4) (i.e. s = 1), output the two solutions r ≡ ± n<sup>(p+1)/4</sup> .
* Step 2: Select a non-square '''z''' such that (z | p) ≡ -1 and set c ≡  z<sup>q</sup> .
* Step 3: Set r ≡ n<sup>(q+1)/2</sup>, t ≡ n<sup>q</sup>, m = s .
* Step 4: Loop the following:
** If t ≡ 1, output '''r''' and '''p - r''' .
** Otherwise find, by repeated squaring, the lowest '''i''', 0 < i < m , such that t<sup>2<sup>i</sup></sup> ≡ 1 .
** Let b ≡ c<sup>2<sup>(m - i - 1)</sup></sup>, and set r ≡ rb, t ≡ tb<sup>2</sup>, c ≡ b<sup>2</sup> and m = i .
</big>


;Task:
Implement the above algorithm. 

Find solutions (if any) for 
* n = 10 p = 13
* n = 56 p = 101
* n = 1030 p = 10009
* n = 1032 p = 10009
* n = 44402 p = 100049  

;Extra credit:
* n  =    665820697     p  =   1000000009      
* n  =   881398088036     p   =  1000000000039    
* n  =  41660815127637347468140745042827704103445750172002   p  = 10^50 + 577   	


;See also:
* [[Modular exponentiation]]
* [[Cipolla's algorithm]]
<br><br>
