The Recognition of Primes

One very important concern in number theory is to establish whether a given number N is prime or composite. At first sight it might seem that in order to decide the question an attempt must be made to factorize N and if it fails, then N is a prime. Fortunately there exist primality tests which do not rely upon factorization. This is very lucky indeed, since all factorization methods developed so far are rather laborious. Such an approach would admit only numbers of moderate size to be examined and the situation for deciding on primality would be rather bad. It is interesting to note that methods to determine primality, other than attempting to factorize, do not give any indication of the factors of N in the case where N turns out to be composite.—Since the prime 2 possesses certain particular properties, we shall, in this and the next chapter, assume for most of the time that N is an odd integer.