13.2 PRIME NUMBERS AND THE SIEVE OF ERATOSTHENES

Eratosthenes (276–194 B.C.E) born in Syene (now Libya) was a Greek geometer. By measuring the sun's angle θ cast by the obelisk at Alexandria and the distance d between Alexandria and Syene, he calculated the circumference of the Earth to be 24,901 miles, as compared to the now accepted value of 29,000 miles, an error of only 17% (Fig. 13.1).

Eratosthenes also invented a sieving1 algorithm to determine all primes ≤N. Begin with the set ODD of odd integers ≤N; for every integer m, remove from ODD the integer m2 and every mth integer following.

image

Figure 13.1 Eratosthenes' measurement of Earth's circumference.

Example 13.1

N = 201 (Tables 13.1 and 13.2); the numbers removed are underlined in Table 13.1. The time needed for sieving is exponential in the number of bits in N, so that Eratosthenes' sieve is not a viable computational method except for small N.

Although there are infinitely many primes, they are rare, in the sense that their density in the set of integers is 0.

Proposition 13.1 (The Prime Number Theorem): The number π(n) of primes less than or equal to n is asymptotic to n/ln n as n → ∞; that is, 1 = limn→∞(π(n))/(n/ln n). This distance between consecutive primes increases much faster than n as n → ∞ so that the density of primes is 0.

There are two central number-theoretic issues in its application to cryptography:

  • efficient ...

Get Computer Security and Cryptography now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.