Prime Numbers

A natural number (positive integer) is prime if it has no factors (that is, 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 · 3² is composite. Finding algorithms for determining if an integer is prime, and the distribution of the prime numbers within the set of natural numbers, are still challenging problems for mathematicians.

There are no computationally efficient algorithms for finding the prime factorization of a given integer (although there are computationally efficient ways of testing whether a given integer is prime -- this is a central idea behind PKE.) Although it has not been proven, computation times for factoring an integer appear to grow exponentially with the size of the integer; whereas it is known that computation times for integer multiplication only grow polynomially. Such problems are examples of what are called NP problems in mathematics. NP type problems are perfect candidates for trap-door functions.