70 lines
1.9 KiB
OCaml
70 lines
1.9 KiB
OCaml
(** Power function implementations for bitarrays *)
|
|
|
|
open Scalable
|
|
open Scalable_basic_arithmetics
|
|
|
|
(* Naive and fast exponentiation ; already implemented in-class in the
|
|
built-in integer case.
|
|
*)
|
|
|
|
(** Naive power function. Linear complexity
|
|
@param x base, a bitarray
|
|
@param n exponent, a non-negative bitarray
|
|
*)
|
|
let pow x n =
|
|
let rec pow_rec x1 n =
|
|
match n with
|
|
[] -> x1
|
|
| n -> pow_rec (mult_b x1 x) (diff_b n [0;1])
|
|
in pow_rec [0;1] n;;
|
|
|
|
(** Fast bitarray exponentiation function. Logarithmic complexity.
|
|
@param x base, a bitarray
|
|
@param n exponent, a non-negative bitarray
|
|
*)
|
|
let power x n =
|
|
if n = [] then [0;1] else
|
|
let rec power_rec x1 n =
|
|
match n with
|
|
[0;1] -> x1
|
|
| n when mod_b n [0;0;1] = [] -> power_rec (mult_b x1 x1) (quot_b n [0;0;1])
|
|
| n -> mult_b x1 (power_rec (mult_b x1 x1) (quot_b (diff_b n [0;1]) [0;0;1]))
|
|
in power_rec x n;;
|
|
|
|
(* Modular expnonentiation ; modulo a given natural (bitarray without
|
|
sign bits).
|
|
*)
|
|
|
|
(** Fast modular exponentiation function. Logarithmic complexity.
|
|
@param x base, a bitarray
|
|
@param n exponent, a non-negative bitarray
|
|
@param m modular base, a positive bitarray
|
|
*)
|
|
let mod_power x n m =
|
|
if n = [] then
|
|
[0;1]
|
|
else
|
|
let rec mod_power_rec c e =
|
|
let c = mod_b (mult_b x c) m
|
|
in if (<<) e n then
|
|
mod_power_rec c (add_b e [0;1])
|
|
else
|
|
c
|
|
in mod_power_rec [0;1] [0;1];;
|
|
|
|
(* 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, a bitarray
|
|
@param n exponent, a non-negative bitarray
|
|
@param p prime modular base, a positive bitarray
|
|
*)
|
|
let prime_mod_power x n p =
|
|
if x = [] then
|
|
[]
|
|
else
|
|
mod_power x (mod_b n (diff_b p [0;1])) p;;
|