Page 283 - Discrete Mathematics and Its Applications

262 4 / Number Theory and Cryptography

of prime numbers to gather evidence concerning the distribution of primes. Using this evidence,
the great mathematicians of the day, including Gauss and Legendre, conjectured, but did not
prove, Theorem 4.

THEOREM 4 THE PRIME NUMBER THEOREM The ratio of the number of primes not exceeding
x and x/ ln x approaches 1 as x grows without bound. (Here ln x is the natural logarithm
of x.)

The prime number theorem was first proved in 1896 by the French mathematician Jacques
Hadamard and the Belgian mathematician Charles-Jean-Gustave-Nicholas de la Vallée-Poussin
using the theory of complex variables. Although proofs not using complex variables have been
found, all known proofs of the prime number theorem are quite complicated.
We can use the prime number theorem to estimate the odds that a randomly chosen number
is prime. The prime number theorem tells us that the number of primes not exceeding x can be
approximated by x/ln x. Consequently, the odds that a randomly selected positive integer less
than n is prime are approximately (n/ln n)/n = 1/ln n. Sometimes we need to find a prime
with a particular number of digits. We would like an estimate of how many integers with a
particular number of digits we need to select before we encounter a prime. Using the prime
number theorem and calculus, it can be shown that the probability that an integer n is prime
is also approximately 1/ ln n. For example, the odds that an integer near 10 1000 is prime are
approximately 1/ln 10 1000 , which is approximately 1/2300. (Of course, by choosing only odd
numbers, we double our chances of finding a prime.)
Using trial division with Theorem 2 gives procedures for factoring and for primality testing.
However, these procedures are not efficient algorithms; many much more practical and efficient
algorithms for these tasks have been developed. Factoring and primality testing have become
important in the applications of number theory to cryptography. This has led to a great interest
in developing efficient algorithms for both tasks. Clever procedures have been devised in the
last 30 years for efficiently generating large primes. Moreover, in 2002, an important theoretical
discovery was made by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. They showed there
is a polynomial-time algorithm in the number of bits in the binary expansion of an integer for
6
determining whether a positive integer is prime.Algorithms based on their work use O((log n) )
bit operations to determine whether a positive integer n is prime.
However, even though powerful new factorization methods have been developed in the
same time frame, factoring large numbers remains extraordinarily more time-consuming than
primality testing. No polynomial-time algorithm for factoring integers is known. Nevertheless,
the challenge of factoring large numbers interests many people. There is a communal effort on
n
the Internet to factor large numbers, especially those of the special form k ± 1, where k is a
small positive integer and n is a large positive integer (such numbers are called Cunningham
numbers). At any given time, there is a list of the “Ten Most Wanted” large numbers of this type
awaiting factorization.

PRIMES AND ARITHMETIC PROGRESSIONS Every odd integer is in one of the two
arithmeticprogressions4k + 1or4k + 3,k = 1, 2,....Becauseweknowthatthereareinfinitely
many primes, we can ask whether there are infinitely many primes in both of these arithmetic
progressions. The primes 5, 13, 17, 29, 37, 41,... are in the arithmetic progression 4k + 1;
the primes 3, 7, 11, 19, 23, 31, 43,... are in the arithmetic progression 4k + 3. Looking at
the evidence hints that there may be infinitely many primes in both progressions. What about
other arithmetic progressions ak + b, k = 1, 2,..., where no integer greater than one divides
both a and b? Do they contain infinitely many primes? The answer was provided by the German
mathematician G. Lejeune Dirichlet, who proved that every such arithmetic progression contains
infinitely many primes. His proof, and all proofs found later, are beyond the scope of this book.