Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
(Add ocaml port) |
m (→{{header|OCaml}}: reduce scope of q; ocamlformat) |
||
| Line 2,680: | Line 2,680: | ||
else |
else |
||
let s = trailing_zeros pp in |
let s = trailing_zeros pp in |
||
| ⚫ | |||
if s = 1 then |
if s = 1 then |
||
let r = pow_mod_p n (succ p / ~$4) in |
let r = pow_mod_p n (succ p / ~$4) in |
||
Some (r, p - r) |
Some (r, p - r) |
||
else |
else |
||
| ⚫ | |||
let z = |
let z = |
||
let rec find_non_square z = |
let rec find_non_square z = |
||
| Line 2,707: | Line 2,707: | ||
in |
in |
||
Some |
Some |
||
(loop (pow_mod_p z q) |
(loop (pow_mod_p z q) (pow_mod_p n (succ q / two)) (pow_mod_p n q) ~$s) |
||
(pow_mod_p n (succ q / two)) |
|||
(pow_mod_p n q) ~$s) |
|||
let () = |
let () = |
||