Prime Number
From iA wiki
See Also: Mathematics | Cryptography
A positive integer with exactly two factors: 1 and the number itself. Thus, 2, 3, 7, 11, 13, 17, 19, 23, 27, 41, and 238877 are prime. 44, for example, is not prime, because 11 is a factor of 44. Numbers like 44 which are not prime are known as composite. The number 1 itself is neither prime nor composite.
Prime numbers have important applications in cryptography, notably in their use in the RSA cipher.
It is perhaps interesting to note that any given number can be broken up as a product of prime numbers in exactly one way. So, for example, 555 is equal to 3×5×37; there is no other list of prime numbers which, when multiplied together, gives 555. This fact is known as the "Fundamental Theorem of Arithmetic."
A fast way to determine if a number is prime is to use the Miller-Rabin algorithm. This algorithm is a probabilistic algorithm; it can prove compositeness with certainty, but primality only with a certain probability. However, this probability can be made as large as desired, and the algorithm itself is quite fast, so it is often used.
