Tonelli-Shanks algorithm
Tonelli–Shanks algorithm
Tonelli-Shanks algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Solve x² ≡ n (mod p)
In computational number theory, the Tonelli–Shanks algorithm is a technique for solving an equation of the form x² ≡ n (mod p), where p is an odd prime and x ,n Є Fp = {0, 1, ... p-1}. It is used in cryptography techniques.
To apply the algorithm we need the Legendre symbol.
Legendre symbol
- The Legendre symbol ( a | p) denotes the value of a ^ ((p-1)/2) (mod p)
- (a | p) ≡ 1 if a is a square (mod p)
- (a | p) ≡ -1 if a is not a square (mod p)
- (a | p) ≡ 0 is a ≡ 0
Algorithm pseudo-code copied from Wikipedia :
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. [Factors out powers of 2 from p-1] Define q -odd- and s such as p-1 = q * 2^s
- if s = 1 , i.e p ≡ 3 (mod 4) , output the two solutions r ≡ +/- n^((p+1)/4) .
- Step 2. Select a non-square z such as (z | p) = -1 , and set c ≡ z^q .
- Step 3. Set r ≡ n ^((q+1)/2) , t ≡ n^q, m = s .
- Step 4. Loop.
- if t ≡ 1 output r, p-r .
- Otherwise find, by repeated squaring, the lowest i , 0 < i< m , such as t^(2^i) ≡ 1
- Let b ≡ c^(2^(m-i-1)), and set r ≡ r*b, t ≡ t*b^2 , c ≡ b^2 and m = i.
Numerical Example
- n=10, p= 13. See Wikipedia
Task
Implement the above.
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: