let EVEN = 
  (fun v1 -> ((v1 mod 2) <= 0)) ;;

type ('a, 'b) prod = 
    Pair of 'a * 'b ;;

let UNIT = 
  (fun v2 -> 
    (fun v1 -> (Pair (v2, v1)))) ;;

let BIND = 
  (fun v4 -> 
    (fun v3 -> 
      (fun v5 -> 
        (match (v4 v5) with 
            (Pair (v2, v1)) -> ((v3 v2) v1))))) ;;

let rec prob_while_cut v2 = 
  (fun v3 -> 
    (fun v4 -> 
      (fun v5 -> 
        (if (v4 <= 0) 
        then (UNIT v5) 
        else 
          (if (v2 v5) 
          then ((BIND (v3 v5)) 
            (fun v1 -> ((((prob_while_cut v2) v3) 
              (let k = (v4 - 1) 
              in 
                (if (k < 0) 
                then 0 
                else k))) v1))) 
          else (UNIT v5)))))) ;;

let K = 
  (fun v2 -> 
    (fun v1 -> v2)) ;;

let I = 
  (fun v1 -> v1) ;;

let many = 
  (fun v1 -> 
    (fun v2 -> ((((prob_while_cut I) (K v1)) v2) true))) ;;

let rec log2 v1 = 
  (if (v1 <= 0) 
  then 0 
  else ((log2 (v1 / 2)) + 1)) ;;

let rec factor_twos v4 = 
  (if ((0 < v4) && (EVEN v4)) 
  then 
    (let v3 = (factor_twos (v4 / 2)) 
    in 
      (match v3 with 
          (Pair (v2, v1)) -> (Pair ((v2 + 1), v1)))) 
  else (Pair (0, v4))) ;;

let rec modexp v5 = 
  (fun v3 -> 
    (fun v4 -> 
      (if (v4 <= 0) 
      then 1 
      else 
        (let v2 = (((modexp v5) v3) (v4 / 2)) 
        in 
          (let v1 = ((v2 * v2) mod v5) 
          in 
            (if (EVEN v4) 
            then v1 
            else ((v1 * v3) mod v5))))))) ;;

let rec witness_tail v2 = 
  (fun v3 -> 
    (fun v4 -> 
      (if (v4 <= 0) 
      then ((v3 = 1) = false) 
      else 
        (let v1 = ((v3 * v3) mod v2) 
        in 
          (if (v1 = 1) 
          then (((v3 = 1) = false) && ((v3 = 
            (let k = (v2 - 1) 
            in 
              (if (k < 0) 
              then 0 
              else k))) = false)) 
          else (((witness_tail v2) v1) (v4 - 1))))))) ;;

let witness = 
  (fun v5 -> 
    (fun v4 -> 
      (let v3 = (factor_twos 
      (let k = (v5 - 1) 
      in 
        (if (k < 0) 
        then 0 
        else k))) 
      in 
        (match v3 with 
            (Pair (v2, v1)) -> (((witness_tail v5) (((modexp v5) v4) v1)) v2))))) ;;

let shd = 
  (fun v1 -> (v1 0)) ;;

let stl = 
  (fun v1 -> 
    (fun v2 -> (v1 (v2 + 1)))) ;;

let rec prob_unif v4 = 
  (fun v5 -> 
    (if (v4 <= 0) 
    then (Pair (0, v5)) 
    else 
      (let v3 = ((prob_unif (v4 / 2)) v5) 
      in 
        (match v3 with 
            (Pair (v2, v1)) -> (Pair (
              (if (shd v1) 
              then ((2 * v2) + 1) 
              else (2 * v2)), (stl v1))))))) ;;

let rec prob_uniform_cut x = 
  (fun x1 -> 
    (fun x2 -> 
      (if (x <= 0) 
      then 
        (if (x1 <= 0) 
        then (raise (Match_failure (string_of_bool true, 0, 0))) 
        else (Pair (0, x2))) 
      else 
        (if (x1 <= 0) 
        then (raise (Match_failure (string_of_bool true, 0, 0))) 
        else 
          (let v3 = ((prob_unif (x1 - 1)) x2) 
          in 
            (match v3 with 
                (Pair (v2, v1)) -> 
                  (if (v2 < x1) 
                  then (Pair (v2, v1)) 
                  else (((prob_uniform_cut (x - 1)) x1) v1)))))))) ;;

let miller_rabin_1 = 
  (fun v4 -> 
    (fun v5 -> 
      (if (v4 = 2) 
      then (Pair (true, v5)) 
      else 
        (if ((v4 = 1) || (EVEN v4)) 
        then (Pair (false, v5)) 
        else 
          (let v3 = (((prob_uniform_cut (2 * (log2 
          (let k = (v4 - 1) 
          in 
            (if (k < 0) 
            then 0 
            else k))))) 
          (let k = (v4 - 2) 
          in 
            (if (k < 0) 
            then 0 
            else k))) v5) 
          in 
            (match v3 with 
                (Pair (v2, v1)) -> (Pair ((((witness v4) (v2 + 2)) = false), v1)))))))) ;;

let miller_rabin = 
  (fun v1 -> 
    (fun v2 -> ((many (miller_rabin_1 v1)) v2))) ;;