🚀 go-pugleaf

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.

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
				CSNET: srt@duke
				ARPA:  srt%duke@csnet-relay