Re: [Caml-list] Errors in Bignum arithmetic?

[Christophe TROESTLER <Christophe.Troestler+ocaml@umh.ac.be>]

On Tue, 10 Aug 2010 08:34:10 -0400, Jim Pryor wrote:
> 
> 3**(561-1) mod 561 = 1
> 5**(1105-1) mod 1105 = 1
> 5**(2465-1) mod 2465 = 1
> 5**(10585-1) mod 10585 = 1
> 
> However, in (my manual Linux x86_64 build of) OCaml 3.12, all of those fail:
> 
> # open Num;;
> # let b1,b3,b5 = num_of_int 1,num_of_int 3, num_of_int 5;;
> val b1 : Num.num = <num 1>
> val b3 : Num.num = <num 3>
> val b5 : Num.num = <num 5>
> # let check p a = let bp,ba = num_of_int p,num_of_int a in
>     let x = mod_num (power_num ba (pred_num bp)) bp in
>     eq_num x b1;;
> val check : int -> int -> bool = <fun>
> # List.map (fun (p,a) -> check p a) [(561,3);(1105,5);(2465,5);(10585,5)];;
> - : bool list = [false; false; false; false]

As a side remark, with Delimited overloading
<https://forge.ocamlcore.org/projects/pa-do/>, your code can read much
clearer:

let check p a =
  Num.(let p = of_int p in
       (of_int a)**(p - 1) mod p = 1);;

You can also easily check your examples in the toplevel -- after
issuing #require "pa_do.num" --

# Num.(3**(561-1) mod 561);;
- : Num.num = <num 375>

My 0.02€,
C.