Tonelli-Shanks algorithm: Difference between revisions
m
added wikipedia tag
Simple9371 (talk | contribs) m (such as --> such that) |
Simple9371 (talk | contribs) m (added wikipedia tag) |
||
Line 1:
{{task}}
{{wikipedia}}
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>
Line 19 ⟶ 20:
;Algorithm pseudo-code
<big>
All ≡ are taken to mean (mod p) unless stated otherwise.
Line 34 ⟶ 35:
** 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>
|