Errors in Bignum arithmetic?

Errors in Bignum arithmetic?

[Jim Pryor]

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

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

[Thomas Fischbacher]

Jim Pryor wrote:

> Hence all of these should hold, with a=3 or 5:
> 
> 3**(561-1) mod 561 = 1

Strange enough, CMU Common LISP, mzscheme and CLISP
give the same left hand side value of 375 here.

-- 
best regards,
Thomas Fischbacher
t.fischbacher@soton.ac.uk

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

[David House]

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]

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

[Jim Pryor]

On Tue, Aug 10, 2010 at 08:46:49AM -0400, David House wrote:
> 
> 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.
> 

On Tue, Aug 10, 2010 at 02:52:19PM +0200, Ronan Le Hy wrote:
> Hello,
> 
> 2010/8/10 Jim Pryor <lists+caml@jimpryor.net>:
> > Fermat's Little Theorem says that when p is prime, then for all 1<=a<p,
> > a**(p-1) mod p = 1. [...]
> >
> > The Carmichael numbers are a series of composites that have the property
> > for all choices of a. http://mathworld.wolfram.com/CarmichaelNumber.html
> 
> This page says "for every choice of a [...] where a and p are
> relatively prime". I believe that explains that your examples below do
> not work :

Excellent, I thought the error was most likely my own. Thanks for identifying it
so quickly.

-- 
Jim Pryor
profjim@jimpryor.net

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

[Ronan Le Hy]

Hello,

2010/8/10 Jim Pryor <lists+caml@jimpryor.net>:
> Fermat's Little Theorem says that when p is prime, then for all 1<=a<p,
> a**(p-1) mod p = 1. [...]
>
> The Carmichael numbers are a series of composites that have the property
> for all choices of a. http://mathworld.wolfram.com/CarmichaelNumber.html

This page says "for every choice of a [...] where a and p are
relatively prime". I believe that explains that your examples below do
not work :

> 3**(561-1) mod 561 = 1
> 5**(1105-1) mod 1105 = 1
> 5**(2465-1) mod 2465 = 1
> 5**(10585-1) mod 10585 = 1

-- 
Ronan

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

[Christophe TROESTLER]

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.