From: hughes@ah.com (Eric Hughes)
Date: Tue, 12 Apr 94 10:02:46 PDT
To: cypherpunks@toad.com
Subject: number theory
In-Reply-To: <199404112346.QAA11556@servo.qualcomm.com>
Message-ID: <9404121652.AA21518@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


The figure I have for the Carmichael numbers is x^(.1), where .1 is
approximate.  Ray has the exponent at 2/7.  The exact one doesn't
matter so much, because compared to the density of primes (x/ln x),
these are both extremely small.  The chance of picking a Carmichael
number is very small.  But that's not the relevant density.

The problem with RSAREF's prime testing is that it will find
pseudoprimes base 2.  Carmichael numbers are pseudoprimes to any base,
but that's unneeded for the RSAREF test.  What is needed is the
density of pseudoprimes base 2.  I don't know that figure.  I don't
know that anybody does.

I would really suggest that someone with access to Mathematica or
Maple do an experiment to find out how many non-primes the RSAREF
algorithm passes.

Carmichael numbers do not, generally, pass the Miller-Rabin test.
Some might; I'll bet it's an open question.

Eric