diff options
| author | Xavier Leroy <xavier.leroy@inria.fr> | 2002-03-14 20:12:54 +0000 |
|---|---|---|
| committer | Xavier Leroy <xavier.leroy@inria.fr> | 2002-03-14 20:12:54 +0000 |
| commit | e26a033cd0eada3c1df1e7ec14544d2a9d8b3977 (patch) | |
| tree | ff2e55d5e93cafa73b52463701f83ec64d8534cf /otherlibs/num/nat.ml | |
| parent | 6d62b988934007b4521dcd6845ccf10b23347d2e (diff) | |
Retour en arriere sur l'exponentiation modulaire, pas correcte
git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@4532 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02
Diffstat (limited to 'otherlibs/num/nat.ml')
| -rw-r--r-- | otherlibs/num/nat.ml | 28 |
1 files changed, 0 insertions, 28 deletions
diff --git a/otherlibs/num/nat.ml b/otherlibs/num/nat.ml index a8ab0f6a9..02f1b1b7a 100644 --- a/otherlibs/num/nat.ml +++ b/otherlibs/num/nat.ml @@ -234,34 +234,6 @@ let sqrt_nat rad off len = loop () end;; -(* Modular exponentiation. Return a fresh nat equal to (a ^ b) mod c. - We assume c > 0 and a < c. *) - -let mod_power_nat a b c = - let len_c = length_nat c in - let res = make_nat len_c in - set_digit_nat res 0 1; - let prod = create_nat (2 * len_c) in - let modmult_res x = - (* res <- res * x mod c *) - let len_x = length_nat x in - set_to_zero_nat prod 0 (2 * len_c); - ignore(mult_nat prod 0 (len_c + len_x) res 0 len_c x 0 len_x); - div_nat prod 0 (len_c + len_x) c 0 len_c; - blit_nat res 0 prod 0 len_c in - let digit = make_nat 1 - and carry = make_nat 1 in - (* Iterate over each bit of b, from most significant to least significant *) - for i = length_nat b - 1 downto 0 do - blit_nat digit 0 b i 1; - for i = 1 to length_of_digit do - modmult_res res; (* res <- res * res *) - shift_left_nat digit 0 1 carry 0 1; - if is_digit_odd carry 0 then modmult_res a (* res <- res * a *) - done - done; - res - let power_base_max = make_nat 2;; match length_of_digit with |