Skip to Main Content

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 \sqrt{n}. So it is enough to check if n is divisible by any one of the primes less than \sqrt{n}. 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 17^2 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 \sqrt{n} / log(\sqrt{n}).

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 10^14. The number of operations to check whether one of them is prime is approximately 10^7/7 = 1.4x10^6, so around 3x10^6 for the two of them. Their product is close to 10^28; to run an exhaustive search for the prime factors of that number would require approximately 10^14/14 = 7x10^12, or about two million times as many operations.

On to the next codes page.

Back to the first codes page.