Errors in Bignum arithmetic?
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Jim Pryor <lists+caml@j...> 
Subject:  Errors in Bignum arithmetic? 
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**(p1) 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**(5611) mod 561 = 1 5**(11051) mod 1105 = 1 5**(24651) mod 2465 = 1 5**(105851) 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