RSA

[mskala at ansuz.sooke.bc.ca]

On Fri, 11 Feb 2000, brian moore wrote:
> Well, you can't really generate a random prime.  In order to do that,
> you'd have to be factoring really large numbers, which is generally
> impracticle (the whole point of RSA is based on the hardness of
> factoring).

Actually, you can prove primality (not just probabilistically) in much
less time than it takes to factor.  For the sizes of primes we use, it may
take a few thousand times as long as the probabilistic tests - i.e.
minutes to hours; NOT years to eons like factoring.

Matthew Skala                       "Ha!" said God, "I've got Jon Postel!"
mskala at ansuz.sooke.bc.ca            "Yes," said the Devil, "but *I've* got
http://www.islandnet.com/~mskala/    all the sysadmins!"