APPLIED NUMBER THEORY

A prime number is an integer bigger than l that has no factor except l and itself. A number that is not prime is called composite. The primality testing problem is to decide whether a given integer is prime or composite. It is considered to be well solved, in contrast to ine factoring problem, which asks for the factorization of a given integer into prime factors. As an example of what can be accomplished with present-day primality tesiing algorithms, we mention the nurnber which consists of 1031 ones. It was proved to be a prime number by H.C. Williams. As another example, consider (2512 + 1) / 2424833 = 552... 209. This number has 148 digits, and with a Computer it is very easy to prove that it is composite. However, no factor of this number is known, except the trivial factors, which are l and the number itself. Most modern primality testing methods depend on Fermat's theorem, which was proved by the French mathematician Pierre de Fermat (1601-1665). It states that every prime number n has the property that an = a mod n for all integers a. Here we müice use of the notation "b = c mod n " which was introduced by Carl Friedrich Gaus