55 lines
2.1 KiB
Text
55 lines
2.1 KiB
Text
|
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''' if '''a''' is a square (mod p)
|
|||
|
|
* '''(a | p) ≡ -1''' if '''a''' is not a square (mod p)
|
|||
|
|
* '''(a | p) ≡ 0''' 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>
|