Prime Numbers in Cryptography

Date: 08/14/99 at 07:03:02
From: Peter Rebernik
Subject: Practical Use of Prime Numbers

What are the practical uses of prime numbers? Is there any real use 
for them other than testing the knowledge of students?

Date: 08/14/99 at 18:45:03
From: Doctor Tom
Subject: Re: Practical Use of Prime Numbers

Hi Peter,

Almost all of the new methods for cryptography depend heavily on prime 
numbers. Some of the best encoding schemes require the product of two 
primes to do the encoding, but require the primes themselves to do the 
decoding. In general, it is FAR more difficult to find the factors of 
a number than to multiply the two numbers, so I can send secret 
messages as follows:

I pick two primes, multiply them together, and give you the product.  
You encode using the product, send me the encoded message, and I can 
decode it because I know the two numbers. This is a "public" method, 
since I can give the product to anyone, so anyone can send me a 
message that only I can read.

The two numbers, by the way, usually are 100 digits long or so, so 
factoring the product might require centuries on a large computer.

In addition, there are dozens of algorithms in computer science that 
depend heavily on prime numbers - hashing schemes, sorting schemes, 
and so on.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/