From: eric@remailer.net (Eric Hughes)
Date: Wed, 28 Dec 94 08:26:08 PST
To: cypherpunks@toad.com
Subject: Re: Are 2048-bit pgp keys really secure ?
In-Reply-To: <9412281539.AA20170@elysion.iaks.ira.uka.de>
Message-ID: <199412281625.IAA02926@largo.remailer.net>
MIME-Version: 1.0
Content-Type: text/plain


   From: danisch@ira.uka.de (Hadmut Danisch)

   > Rabin-Miller would be better.  It would be instructive to examine the
   > conditional probability that a composite number which fails
   > Rabin-Miller passes Fermat.  I understand it's vanishingly small.

   What is "vanishingly small" ?

Small enough to ignore for the practice of "pretty good" security.

There are algorithms to prove primality.  See Cohen's excellent _A
Course in Computational Algebraic Number Theory_, from Springer.

   Does anyone know how many Carmichael-Numbers exist?

An infinite number.  This was just proven in the last two years.  The
density of Carmichael numbers is very small.  As I recall, this paper
also included Pomerance, but I don't remember if he did the bulk of
the work or not.

   If you found a Carmichael-Number consisting of primes bigger than
   the primes in your small-numbers-sieve, the Fermat-test won't detect
   it as a non-prime.

Miller-Rabin will, however.  Since most of the time generating a
modulus has to do with testing composites, the added time for a few
more modexp's to do M-R is small.  The large effort is that of the
authors of the crypto package to implement and debug it.

Eric