[24566] in Cypherpunks
Re: Are 2048-bit pgp keys really secure ?
daemon@ATHENA.MIT.EDU (Eric Hughes)
Wed Dec 28 11:38:10 1994
Date: Wed, 28 Dec 1994 08:25:59 -0800
To: cypherpunks@toad.com
In-Reply-To: <9412281539.AA20170@elysion.iaks.ira.uka.de> (danisch@ira.uka.de)
From: eric@remailer.net (Eric Hughes)
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
