A whole number greater than 1 whose only factors are 1 and itself is referred to as a prime number. A whole number that can be divided evenly into another number is referred to as a factor. 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 are the first few prime numbers. Composite numbers are those that have more than two factors. Neither prime nor composite, number one.
There is a prime number called up that exists for every prime number, such as “p,” and is greater than p. The idea that there is no “largest” prime number is supported by this mathematical demonstration, which was made in antiquity by the Greek mathematician Euclid. Prime numbers do tend to become less common and more challenging to locate in a reasonable amount of time as the set of natural numbers N = 1, 2, 3,… progresses.
How to figure out whether a number is a prime number
Extremely large numbers can be tested on a computer to see if they are prime. However, testing in this way will eventually become too difficult, even for the most powerful supercomputers, because there is no upper bound on the size of a natural number. As an illustration, in December of 2018, there were 24,862,048 digits in the largest known prime number.
Many algorithms have been developed to produce ever-larger prime numbers. Consider the case where “n” is a whole number and it is unknown whether it is prime or composite. Take n’s square root, or the 1/2 power, and then round it up to the next highest whole number. The resulting number is called m. Then, determine each of the quotients listed below:
QM = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2
If — and only if — none of the derived qs are whole numbers, then the number n is prime.
Fermat and Mersenne prime numbers
Any number that can be reduced to the form 2 n – 1, where n is a prime number, is said to be a Mersenne prime. The first few values of n that are known to result in Mersenne primes are: 2, 3, 5, 7, 13, 17, 19, n = 31, n = 61, and n = 89.
A Fermat number that is also prime is known as a Fermat prime. The form of a Fermat number F n is 2 m + 1, where m denotes a power of 2 (m = 2 n), and n is an integer.
Prime numbers and cryptography
Encryption follows a fundamental principle: the key needs to be kept secret, not the algorithm, or the actual procedure being used. Key creation can benefit greatly from prime numbers. For instance, the fact that it is simple to calculate the product of two prime numbers chosen at random illustrates the strength of public/private key encryption. However, when only the product is known, it can be very challenging and time-consuming to figure out which two prime numbers were used to produce an extremely large product.
Prime numbers are always supposed to be unique in the well-known public key cryptography algorithm RSA (Rivest-Shamir-Adelman). However, the primes employed by the Diffie-Hellman key exchange and Digital Signature Standard (DSS) cryptography schemes are regularly standardized and are employed by a wide range of applications.
