Tonelli-Shanks algorithm: Difference between revisions
m
such as --> such that
Simple9371 (talk | contribs) (Beautified task description (check check for errors)) |
Simple9371 (talk | contribs) m (such as --> such that) |
||
Line 25:
* 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
** 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> .
Line 31:
* 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
** 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>
| |||