Prime Numbers

Introduction

The second classification of the natural numbers, after the classification of even and odd, is prime numbers. The Fundamental Theorem of Arithmetic, sometimes called the Unique Factorization Theorem as described below in more detail, states that any and every integer is either uniquely a product of prime numbers or is a prime number. One of the beauties of number theory is that, since prime numbers can play the role of generator, every integer has a unique signature, the collection of its prime divisors.

A prime number is any positive integer P > 1 where P's only divisors are ± 1 and ± P. All other integers are composite except for 0 and ± 1, which are neither prime nor composite. Furthermore, the concept of primeness can extend to negative integers less than -1. Public key cryptosystems such as RSA, make use of very large primes for its key generations.

Trial Division

The most common way to find out whether or not an integer N is prime is by trial division. In other words, divide N by all of the numbers from 2 to └√N┘ until either a division with remainder 0 occurs or the total numbers to use has been exhausted. However, the time complexity for this process is exponential θ(√N). As a matter of fact, there does not exist a polynomial time bounded algorithm that is able to find factors of integers, thus considering this problem in the complexity class NP.

Prime Number Theorem

The prime distribution function π(N) is the total number of primes ≤ N. For example, π(10) = 4. The Prime Number Theorem states:

Lim (N -> ∞) π(N)/(N/ln(N)) = 1

The Prime Number Theorem is an approximation that is reasonably accurate, which can be used to estimate with the probability of 1/ln(N) that a randomly chosen integer N is prime. The Prime Number Theorem states that the primes near a prime are spaced on the average one every (ln(N))/2 integers. The 1/2 considers that even numbers don't count. For instance, a 512-bit prime number would require ln(2⁵¹²)/2 or roughly 178 512-bit random numbers for primality testing.

Miller-Rabin

So with this, the next best thing to obtaining large prime numbers is to play the probability game by choosing an arbitrarily large odd integer say 2285760293497823444790323455592340983477 and conduct the Miller-Rabin primality test or some other primality test of your choice. Again, keep in mind, primality tests for large numbers, are based on a confidence level because there isn't an absolute proven way to yield arbitrarily large prime numbers.

The Miller-Rabin process tests 2 input values X and Y such that X is the integer in question and X > 2 | X is odd, and n is the total number of random integer values chosen for comparison | 1 ≤ Y < X. A random number generator picks a random integer R | 1 ≤ R ≤ X - 1. A subroutine called "Witness" is then used to prove that X is composite. Witness takes 2 input values as well, R and X, and is based on Fermat's theorem. If Witness returns TRUE then X is a composite, which is provable. However, if Witness returns FALSE then it is highly likely that X is prime. The reason why it isn't absolute is because there exists a small probability that the algorithm might not have picked an R that would return a TRUE. So, the Miller-Rabin algorithm depends on the size of Y and a little luck in choosing random base values R. The following is a more precise theorem [8a]:

If N is an odd composite number, then the number of witnesses to the compositeness of N is at least (N - 1) / 2.

Mersenne Primes

Another form of prime numbers is the Mersenne prime numbers. Mersenne Primes are related to the perfect number concept. A perfect number is an integer such that the sum of its own divisors is twice the number. For instance, 6 is a perfect number because when its divisors are added together we have 1 + 2 + 3 + 6 = 12. Euclid demonstrated that if MP is a Mersenne prime then MP(MP + 1) / 2 is a perfect number. Many centuries later, Euler proved that any even perfect numbers have this form, however, no odd perfect numbers are known. Anyway, the Mersenne prime number is defined by:

(2^P) - 1 such that P must be prime

Only 39 Mersenne primes have been identified to date, so the question whether there is a finite or infinite number of primes of this form goes unanswered. Because fast algorithms exist for finding Mersenne primes, the largest known prime numbers today are Mersenne primes. In fact, the largest known prime number (2^13466917) - 1 is a Mersenne prime, which was discovered by a distributed computing effort, called the Great Internet Mersenne Prime Search.

Fundamental Theorem of Arithmetic

GCD

The Greatest Common Divisor is the largest integer or common divisor that divides 2 or more integers. The GCD can also be calculated using the FTA. The product of all prime factors common to both sets of prime factorizations of the integers being tested will produce the GCD. For example, the procedure for finding the GCD of 24 and 60 is:

24 = 2 x 2 x 2 x 3
60 = 2 x 2 x 3 x 5

yields a GCD of

12 = 2 x 2 x 3

such that 2, 2, 3 exists in both factorizations. If no prime factors are in common then only the integer 1 is the common divisor hence 1 is the GCD. For example the GCD of 18 and 175 yields no common prime factors because 18 = 2 x 3 x 3 where as 175 yields 5 x 5 x 7.

LCM

The Least Common Multiple of 2 or more integers is the smallest integer that those 2 or more integers divides. The FTA can also be used here to find the LCM by taking the product of all different prime factors of those 2 or more integers, where each listed as a factor the maximum number of times it appears in those 2 or more integers. For example, the LCM of 12 and 18 is:

12 = 2 x 2 x 3
18 = 2 x 3 x 3

yields a LCM of

36 = 2 x 2 x 3 x 3

Another example is the following:

99 = 3 x 3 x 11
350 = 2 x 5 x 5 x 7

yields a LCM of

34,650 = 2 x 3 x 3 x 5 x 5 x 7 x 11

Relatively Prime Numbers

When taking the GCD(x,y), x and y are relatively prime if their only common factor is 1. For instance, 9 and 14 are relatively prime because the highest GCD is 1.

Links

http://www.mersenne.org/prime.htm
http://www.math.umd.edu/~krc/numbers/prime.html
http://www.math.utah.edu/~alfeld/math/prime.html
http://www.ontko.com/~rayo/primes/
http://web.tiscali.it/GEB/sfteng.htm
http://www.loria.fr/~zimmerma/records/primes.html
http://www.nist.gov/dads/HTML/millerRabin.html
http://home.ecn.ab.ca/~jsavard/crypto/pk050201.htm
http://www.wikipedia.org/wiki/Prime_number
http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/Prime_numbers.html