Primality Testing: An Overview
Birkhäuser Boston eBooks · 2007
In the previous two chapters we have seen that there are infinitely many primes and showed that as we move through larger and larger integers the density of primes thins out. In particular, we proved that where π ( x ) represents the number of primes less than the positive real number x . This result, the prime number theorem, could be interpreted as saying that the probability of randomly choosing a prime number less than or equal to a positive real number x is approximately 1/ln x as x gets large. In this chapter we consider the question of determining whether a particular given positive integer n is prime or not prime. The methods concerning this problem are called primality testing and consist of algorithms to determine whether an inputted positive integer is prime. Primality testing has become extremely important and has been of great interest in recent years due to its close ties to cryptography and especially public key cryptography . Cryptography is the science of encoding and decoding secret messages. Many of the most powerful and secure encoding methods depend on number theory, especially on the computational difficulty of factoring large integers. It turns out, somewhat surprisingly, that relative to ease of computation, determining whether a number is prime is easier than actually factoring it. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.