🚀 go-pugleaf

In article <615@mit-amt.MEDIA.MIT.EDU> simsong@media-lab.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.
>

Once again, quoting the original paper:

=====================================

VII(B). How to Find Large Prime Numbers

	...

  To find a 100-digit "random" prime number, generate (odd) 100-digit
random numbers until a prime number is found.  By the prime number
theorem[9], about (ln 10**100)/2 == 115 numbers will be tested before
a prime is found.

   To test a large number 'b' for primality we recommend the elegant
"probabilistic" algorithm due to Solovay and Strassen[14].  It picks a
random number 'a' from a uniform distribution on {1,...,b-1}, and tests
whether

	gcd(a,b) = 1 and J(a,b) == a**((b-1)/2) mod b		(6)

where J(a,b) is the Jacobi symbol[9].  If b is prime (6) is always true.
If b is composite (6) will be false with probability at least 1/2.  If
(6) holds for 100 randomly chosen values of a, then b is almost
certainly prime; there is a (negligible) chance of one in 2**100 that
b is composite.  Even if a composite were accidentally used in our
system, the receiver would probably detect this by noticing that
decryption didn't work correctly.

	...

Note that this algorithm does *not* test a number for primality by trying
to factor it.  Other efficient procedures for testing a large
number for primality are given in [8,11,13].


references:

[9] Niven, I., and H.S. Zuckerman.  "An Introduction to the Theory of Numbers".
(John Wiley & Sons, New York 1972).

[14] Solovay, R. and V. Strassen. "A Fast Monte-Carlo Test for Primality",
SIAM Journal on Computing (March 1977), 84-85.

=====================================

For those who care, the original paper is

    A Method for Obtaining digital Signatures and Public-Key Cryptosystems
		by R.L. Rivest, A. Shamir, and L. Adleman
		  MIT Laboratory for Computer Science
			Technical Memo LCS/TM82
			Cambridge, Mass. 02139
		April 4, 1977 (Revised December 12, 1977)


You should be able to get a copy through MIT Press.  The first edition was
400 copies which ran out quickly (they had 4000 requests).  The Federal
government censored the paper for a while, and MIT had to go to court to
be able to print further copies.  (My copy is 2nd edition).


		-ed falk, sun microsystems
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.
(The above is food for the NSA line eater.)