From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <lists+caml@jimpryor.net>
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id C561BBBAF
	for <caml-list@yquem.inria.fr>; Tue, 10 Aug 2010 14:32:52 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AscAAN3jYExCbwQZkWdsb2JhbACTYYx2FQEBAQEJCwoHEQQewlMFhTqJPoJe
X-IronPort-AV: E=Sophos;i="4.55,348,1278280800"; 
   d="scan'208";a="65233868"
Received: from out1.smtp.messagingengine.com ([66.111.4.25])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 10 Aug 2010 14:32:52 +0200
Received: from compute1.internal (compute1.internal [10.202.2.41])
	by gateway1.messagingengine.com (Postfix) with ESMTP id 3ADBB549
	for <caml-list@yquem.inria.fr>; Tue, 10 Aug 2010 08:32:51 -0400 (EDT)
Received: from frontend1.messagingengine.com ([10.202.2.160])
  by compute1.internal (MEProxy); Tue, 10 Aug 2010 08:32:51 -0400
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=messagingengine.com; h=date:from:to:subject:message-id:mime-version:content-type; s=smtpout; bh=+lBiRCYhzcl1mUii9WvJ6TuBRK4=; b=OLhQXSU2LIyjyrOASIi8V7284vyjXFVf9De3t780JNCLimQV+MeyZDgFK445Hdd62WUousUyHwXOY3wLPzWGQb8+PHL0UWUMPqz0C9WUJz/5bnfetGhoFDGuFL85QTsq08Cv/74WslB7MveE05krdaBRvucv+x+9tdK5WNwayUg=
X-Sasl-enc: uLQAU0xecTOchgxYUqO2MJlbTBxH+x+dafjiNwU3DIGa 1281443570
Received: from localhost (unknown [69.86.121.157])
	by mail.messagingengine.com (Postfix) with ESMTPSA id 9FEC14008C1
	for <caml-list@yquem.inria.fr>; Tue, 10 Aug 2010 08:32:50 -0400 (EDT)
Date: Tue, 10 Aug 2010 08:34:10 -0400
From: Jim Pryor <lists+caml@jimpryor.net>
To: caml-list@yquem.inria.fr
Subject: Errors in Bignum arithmetic?
Message-ID: <20100810123410.GC16292@vaio.jimpryor.net>
Mail-Followup-To: caml-list@yquem.inria.fr
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.20 (2009-06-14)
X-Spam: no; 0.00; bignum:01 bignum:01 bug:01 ocaml:01 val:01 val:01 pred:01 bool:01 bool:01 modular:01 arithmetic:01 arithmetic:01 wolfram:01 int:01 int:01 

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