English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    
Browse thread
Errors in Bignum arithmetic?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: David House <dmhouse@g...>
Subject: Re: [Caml-list] Errors in Bignum arithmetic?
On 10 August 2010 08:34, Jim Pryor <lists+caml@jimpryor.net> wrote:
> 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.

You've missed a small detail in the definition here. n is Carmichael
iff a^(n-1) = 1 (mod n) for all a with gcd(a,n) = 1; in other words,
you are only allowed to consider a's which are coprime to your
supposed Carmichael number.

And indeed,

# let rec gcd a b = if b = 0 then a else gcd b (a mod b);;
val gcd : int -> int -> int = <fun>
# List.map (fun (a,b) -> gcd a b) [561,3; 1105,5; 2465,5; 10585,5];;
- : int list = [3; 5; 5; 5]