(** 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;;