Prime Numbers

A natural number (positive integer) is prime if it has no factors (numbers whose product
is the given number), other than itself and 1. If a number is not prime, it is called
composite (for example, 17 is prime, but 18 = 2 × 32 is composite). Finding algorithms for determining if an integer is prime and the distribution of the prime numbers within a
set of natural numbers are still major challenges for mathematicians. There are no computationally
efficient algorithms for finding the prime factorization of a given integer.
There are, however, computationally efficient ways of testing whether a given integer
is prime. This is central to PKE systems.
Although unproven, computation times for factoring an integer grow exponentially
with the size of the integer, whereas computation times for integer multiplication grow
only polynomially. 212