🚀 go-pugleaf

Simson 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.

Come on, Simson. Have you never heard of probablistic factorization?
Or read Michael Rabin's paper _Probablistic Algorithm for 
Testing Primality_ ? 

To be more precise, I would say "The only way to *prove* if a 
100-digit number is prime with 100% certainty is to factor it (or
*prove* no factors exist). We can *show* a number to be prime with
very high likelihood (as high as you have the computer resources
to test) by applying Rabin's algorithm."

[Aside from a former to MIT student to another: Mattuck showed Rabin's
algorithm in 18.063, and Shafi covered it in detail in 6.875, which
is a good graduate course in cryptography.]

Sam Levitin	Levitin%SEMI.DEC@decwrl		[MIT '85, '86]
DEC Hudson-LSI	77 Reed Road, Hudson MA 01749	(617) 568-4135