Anonymous user
Tonelli-Shanks algorithm: Difference between revisions
Add ocaml port
(Replaced deprecated "ArithmeticError" with "ValueError". Added some spaces to improve readability.) |
(Add ocaml port) |
||
Line 2,664:
30468 69581
378633312 621366697</pre>
=={{header|OCaml}}==
{{trans|Java}}
{{libheader|zarith}}
An extra test case has been added for the `s = 1` branch.
<lang ocaml>let tonelli n p =
let open Z in
let two = ~$2 in
let pp = pred p in
let pph = pred p / two in
let pow_mod_p a e = powm a e p in
let legendre_p a = pow_mod_p a pph in
if legendre_p n <> one then None
else
let s = trailing_zeros pp in
let q = pp asr s in
if s = 1 then
let r = pow_mod_p n (succ p / ~$4) in
Some (r, p - r)
else
let z =
let rec find_non_square z =
if legendre_p z = pp then z else find_non_square (succ z)
in
find_non_square two
in
let rec loop c r t m =
if t = one then (r, p - r)
else
let mp = pred m in
let rec find_i n i =
if n = one || i >= mp then i else find_i (n * n mod p) (succ i)
in
let rec exp_pow2 b e =
if e <= zero then b else exp_pow2 (b * b mod p) (pred e)
in
let i = find_i t zero in
let b = exp_pow2 c (mp - i) in
let c = b * b mod p in
loop c (r * b mod p) (t * c mod p) i
in
Some
(loop (pow_mod_p z q)
(pow_mod_p n (succ q / two))
(pow_mod_p n q) ~$s)
let () =
let open Z in
[
(~$9, ~$11);
(~$10, ~$13);
(~$56, ~$101);
(~$1030, ~$10009);
(~$1032, ~$10009);
(~$44402, ~$100049);
(~$665820697, ~$1000000009);
(~$881398088036, ~$1000000000039);
( of_string "41660815127637347468140745042827704103445750172002",
pow ~$10 50 + ~$577 );
]
|> List.iter (fun (n, p) ->
Printf.printf "n = %s\np = %s\n%!" (to_string n) (to_string p);
match tonelli n p with
| Some (r1, r2) ->
Printf.printf "root1 = %s\nroot2 = %s\n\n%!" (to_string r1)
(to_string r2)
| None -> print_endline "No solution exists\n")
</lang>
{{out}}
<pre>
n = 9
p = 11
root1 = 3
root2 = 8
n = 10
p = 13
root1 = 7
root2 = 6
n = 56
p = 101
root1 = 37
root2 = 64
n = 1030
p = 10009
root1 = 1632
root2 = 8377
n = 1032
p = 10009
No solution exists
n = 44402
p = 100049
root1 = 30468
root2 = 69581
n = 665820697
p = 1000000009
root1 = 378633312
root2 = 621366697
n = 881398088036
p = 1000000000039
root1 = 791399408049
root2 = 208600591990
n = 41660815127637347468140745042827704103445750172002
p = 100000000000000000000000000000000000000000000000577
root1 = 32102985369940620849741983987300038903725266634508
root2 = 67897014630059379150258016012699961096274733366069
</pre>
=={{header|Perl}}==
| |||