p

(** Power function implementations for built-in integers *)

#use "builtin";;
#use "basic_arithmetics";;

(* Naive and fast exponentiation ; already implemented in-class.
 *)

(** Naive power function. Linear complexity
    @param x base
    @param n exponent
 *)
let pow x n = (
    let rec _pow ?(i=1) x n = (
        if
          n = 0 then 1
        else
          if i = n then
              x
          else
              x*(_pow ~i:(i+1) x n )
    ) in
        _pow x n
);;

(** Fast integer exponentiation function. Logarithmic complexity.
    @param x base
    @param n exponent
 *)
let power x n = (
    let rec _power num =(function
        (*This function was in the seminary, so it is likely that other people will have the same*)
      | 0 -> 1
      | 1 -> num
      | n ->
        let b = _power num (n / 2) in
            b * b * (if n mod 2 = 0 then 1 else num)
    ) in
        _power x n
);;

(* Modular expnonentiation ; modulo a given natural number smaller
   max_int we never have integer-overflows if implemented properly.
 *)

(** Fast modular exponentiation function. Logarithmic complexity.
    @param x base
    @param n exponent
    @param m modular base
 *)
let mod_power x n m = (
    let
      rec _mod_power num n =(
        match n with
          | 0 -> 1
          | 1 -> num
          | x ->
            let b = (_mod_power num (x / 2)) in
                modulo (b * b * (if x mod 2 = 0 then 1 else num)) m
      )
    in
      modulo (_mod_power x n) m
);;

(* Making use of Fermat Little Theorem for very quick exponentation
   modulo prime number.
 *)

(** Fast modular exponentiation function mod prime. Logarithmic complexity.
    It makes use of the Little Fermat Theorem.
    @param x base
    @param n exponent
    @param p prime modular base
 *)
let prime_mod_power x n p = (
  if x = 0 then
    0
  else
    let
      rec _prime_mod_power num n =(
        match n with
          | 0 -> 1
          | 1 -> num
          | x when x = p-1 -> 1
          | x ->
            let b = (_prime_mod_power num (x / 2)) in
                modulo (b * b * (if x mod 2 = 0 then 1 else num)) p
        )
      in
        modulo (_prime_mod_power x n) p
);;