(** Testing for primality *)

open Builtin
open Basic_arithmetics
open Power

(** Deterministic primality test *)
let is_prime n =
  if n = 2 || n = 3 then
    true
  else
    if modulo n 2 = 0 || modulo n 3 = 0 then
      false
    else
      let rec is_prime_rec k =
        if (6*k-1) * (6*k-1) > n then
          true
        else
          match (6*k-1, 6*k+1) with
              (a, b) when modulo n a = 0 || modulo n b = 0 -> false
            | _ -> is_prime_rec (k+1)
      in is_prime_rec 1;;

(** Pseudo-primality test based on Fermat's Little Theorem
    @param p tested integer
    @param testSeq sequence of integers againt which to test
 *)

let is_pseudo_prime p test_seq =
    let rec is_pseudo_prime_rec l =
      match l with
          [] -> true
        | e::l1 when mod_power e (p-1) p <> 1 -> begin
          if gcd e p = 1 then
            false
          else
            is_pseudo_prime_rec l1
        end
        | _::l1 -> is_pseudo_prime_rec l1
    in is_pseudo_prime_rec test_seq;;