Prime Numbers

(1)
Prime Numbers
Description
Asymmetric encryption methods rely heavily on the use of prime numbers, usually exceedingly long primes, for their operation. By definition, prime numbers are divisible only by themselves and 1. In other words, letting the symbol | denote divisibility (i.e. - a | b means "b divides into a"), a prime number strictly adheres to the following mathematical definition
| Where or only
The Fundamental Theorem of Arithmetic states that all integers can be decomposed into a unique prime factorization. Any integer greater than 1 is considered either prime or composite. A composite number is composed of more than one prime factor
| where ultimately
in which is a unique prime number and is the exponent.
Numerical Examples
543,312 = 24 32 50 73 111
553,696 = 25 30 50 70 113 131
As can be seen, according to this systematic decomposition, each factorization is unique.
In order to deterministically verify whether an integer is prime or composite, only the primes need be examined. This type of systematic, thorough examination is known as a brute-force approach. Primes and composites are noteworthy in the study of cryptography since, in general, a public key is a composite number which is the product of two or more primes. One (or more) of these primes may constitute the private key.
There are several types and categories of of prime numbers, three of which are of importance to cryptography and will be discussed here briefly.
Fermat Primes
Fermat primes take the following form

Note that not all Fermat "primes" are, in fact, prime. The [1] Wolfram Alpha engine reports Fermat Primes, an example input request being "4th Fermat Prime".
Numerical Examples






The Fermat primes are indeed prime numbers. However, the absolute "primeness" of Fermat primes was disproven by Euler when he showed F5 = 641.6,700,297 demonstrating that this Fermat prime was in fact, composite.

Mersenne Primes
Mersenne primes - another type of formulaic prime generation - follow the form

where is a prime number. The Wolfram Alpha engine reports Mersenne Primes, an example input request being "4th Mersenne Prime".
Numerical Examples
The first five Mersenne primes are as follows





It is easily shown that , meaning that all Mersenne primes are not in fact prime, as was the case with Fermat primes.
Coprimes (Relatively Prime Numbers)
Two numbers are said to be coprime if the largest integer that divides evenly into both of them is 1. Mathematically, this is written

where (gcd) is the greatest common divisor. Two rules can be derived from the above definition
If | and , then |
If with , then both and are squares, i.e. - ,
The Prime Number Theorem
The Prime Number Theorem estimates the probability that any integer, chosen randomly will be prime. The estimate is given below, with defined as the number of primes

is asymptotic to , that is to say . What this means is that generally, a randomly chosen number is prime with the approximate probability .