Errors in Bignum arithmetic?

[Jim Pryor <lists+caml@jimpryor.net>]

Hi, I think I've identified some arithmetic errors in the behavior of
the Bignum libraries. I may well be making some mistake of my own,
though, so I thought I'd expose this to a few more eyes before making it
a bug report.

Background:

Fermat's Little Theorem says that when p is prime, then for all 1<=a<p,
a**(p-1) mod p = 1. However, some composite p also have this property
for some choices of a. However, if one checks a handful of a, only a few
composite p will have the property wrt all of them. This is the basis of
one fairly reliable indeterministic test for primality.

The Carmichael numbers are a series of composites that have the property
for all choices of a. http://mathworld.wolfram.com/CarmichaelNumber.html tells us the first few Carmichael numbers are [561; 1105; 1729; 2465; 2821; 6601; 8911; 10585; 15841; 29341]. Conceivably there's a typographical mistake in that list, but I've seen the segment of it < 10k also reported elsewhere.

Hence all of these should hold, with a=3 or 5:

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]

(I realize there are more efficient methods to do modular
exponentiation; but I'm trying to reduce the number of variables here.)

The other Carmichael numbers in my list, and all primes up to 10k, do
behave as expected for a=2,3 and 5.

-- 
Jim Pryor
profjim@jimpryor.net