From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Fri Jun 14 2002 - 04:04:30 MDT
spike66 wrote:
>>
>> Wei Dai writes
>>
>>> On the other hand, consider the product of {3, 5, 7, 11, 389, 29959,
>>> 128194589, 566684450325197, 29753376105337343078941364947,
>>> 30082232218581187462432471034748868284388270918928732239}.
>>>
> Just a minute, Wei. This last factor has 187 bits. To prove primeness
> using a 2.4 ghz P4 would take 11 weeks by the best known factoring
> algorithm. The Olympic committee suspects you of steroid abuse, pal.
> {8^D spike
There are tests for primeness that don't use factoring; they are
probabilistic rather than absolute tests, but you can obtain a very high
probability of primeness by applying the tests repeatedly. That's how PGP
generates 4096-bit private keys in less than the age of the universe.
-- Eliezer S. Yudkowsky http://singinst.org/ Research Fellow, Singularity Institute for Artificial Intelligence
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:14:47 MST