(** Testing for primality *)

open Scalable
open Scalable_basic_arithmetics
open Scalable_power

(** Deterministic primality test *)
let is_prime n =
  if n = [0;0;1] || n = [0;1;1] then
    true
  else
    if mod_b n [0;0;1] = [] || mod_b n [0;1;1] = [] then
      false
    else
      let rec is_prime_rec k =
        let test_inf = diff_b (mult_b [0;0;1;1] k) [0;1] in
        let test_sup = add_n test_inf [0;0;1] in
        if (>>) (mult_b test_inf test_inf) n then
          true
        else
          match (test_inf, test_sup) with
              (a, b) when mod_b n a = [] || mod_b n b = [] -> false
            | _ -> is_prime_rec (add_n k [0;1])
      in is_prime_rec [0;1];;

(** Pseudo-primality test based on Fermat's Little Theorem
    @param p tested bitarray
    @param testSeq sequence of bitarrays 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 (diff_b p [0;1]) p <> [0;1] -> begin
          if gcd_b e p = [0;1] then
            false
          else
            is_pseudo_prime_rec l1
        end
        | _::l1 -> is_pseudo_prime_rec l1
    in is_pseudo_prime_rec test_seq;;