From Euclid to public-key codes 2 From Euclid and Euler to Public-Key Codes
How to find out if a given number is prime; how to find a factor if it is composite
The study of primes and divisibility goes back at least to Euclid. In his Elements Euclid proves, for example, that there are infinitely many prime numbers (Book IX, Proposition 20). The link is to the beautiful Web site Euclid's Elements, posted by David Joyce (Clark University).
Traditionally, the two questions in the title refer to the same problem: you test all possible factors (it is clearly enough to test all possible prime factors). If one of them divides your number evenly, that's your factor; if none of them works, the number is prime. (Today there are ways of getting high-confidence answers to the second question without touching the first: see Industrial-Grade Primes.)
If a number n is composite, it must have at least one prime factor less than
. So it is enough to check if n is divisible by any one of the primes less than
. For example, to see that 193 is prime, it is enough to check that it is not divisible by 2, 3, 5, 7, 11, 13, since
is too big. In general, the number of primes less than k is approximately k / log k (this is the Prime Number Theorem), so the number of primes we need to check to see if n is prime is approximately
/ log(
).
In practice there are much better methods for finding a factor: see A Tale of Two Sieves by Carl Pomerance. But the following example, using primitive methods, gives an idea of how much harder it is, in general, to factor than to multiply.
For example, suppose we are using two 15-digit numbers, both close to
. The number of operations to check whether one of them is prime is approximately
, so around
for the two of them. Their product is close to
; to run an exhaustive search for the prime factors of that number would require approximately
, or about two million times as many operations.
On to the next codes page.
Back to the first codes page.
Welcome to the
Feature Column!
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .
Feature Column at a glance