The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   
Associated Topics:
High School Number Theory
Middle School Prime Numbers

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.