🚀 go-pugleaf

In article <9087@duke.duke.UUCP>, srt@duke.UUCP writes:
>In article <615@mit-amt.MEDIA.MIT.EDU>, simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) writes:
>> WAIT! It is not "easy" to test a 100-digit number for priamity.
>> How do you do that? To tell if a number is prime or not, you factor it.
>> 			Simson L. Garfinkel
>> 			MIT Media Lab
>No, no, no, no, no, no......  Not true at all.  There are many ways to test
>if a number is prime that do not involve factoring.  Lenstra's theorem provides
>a fairly quick test, and Shafi Goldwasser at MIT also came up with a fairly
>efficient test using elliptic groups.

Wai-wai-wait... an earlier posting in this group showing a method that
purported to be based on Lenstra's theorem simply produced a big number which
is PROBABLY prime, to a degree of probability asymptotically approaching 100%
depending on the number of iterations successfully passed in the test.  How
is this different from the statement below "And if you don't mind the pos-
sibility of error (which you can make very small)..."?

>And if you don't mind the possibility of error (which you can make very small),
>you can use some of the randomized algorithms such as the strong pseudoprime
>test and the Solovay-Strassen primality test.  This is what probably all
>RSA shemes use for selecting p & q.....
>Steve Tate			UUCP: ..!{ihnp4,decvax}!duke!srt
-- 
 -------------------------------    Disclaimer:  The views contained herein are
|            dan levy            |  my own and are not at all those of my em-
|         an engihacker @        |  ployer or the administrator of any computer
| at&t computer systems division |  upon which I may hack.
|        skokie, illinois        |
 --------------------------------   Path: ..!{akgua,homxb,ihnp4,ltuxa,mvuxa,
                                        allegra,ulysses,vax135}!ttrdc!levy