30 lines
598 B
OCaml
30 lines
598 B
OCaml
(** Factoring Built-In Int Primes *)
|
|
|
|
open Builtin
|
|
open Basic_arithmetics
|
|
|
|
(** Factors product of two primes.
|
|
@param key is public key of an RSA cryptosystem.
|
|
*)
|
|
|
|
let break (n, e) =
|
|
if n = 6 then
|
|
(2,3)
|
|
else
|
|
let rec break_rec k plus=
|
|
let prime =
|
|
if plus then
|
|
6 * k + 1
|
|
else
|
|
6 * k - 1
|
|
in if modulo n prime = 0 then
|
|
(prime, quot n prime)
|
|
else
|
|
let (k, plus) =
|
|
if plus then
|
|
(k+1, false)
|
|
else
|
|
(k, true)
|
|
in break_rec k plus
|
|
in break_rec 1 false;;
|