**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 website
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 as well as
What are the
best factoring methods in use today
(learn also about the
RSA Factoring Challenge).
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.

© copyright 1999, American Mathematical Society.