Primality and Factorization, An Introduction

Introduction

The fundamental theorem of arithmetic says that numbers factor uniquely into primes. Given this, are there efficient procedures for determining whether a number is prime? Can we split a composite number into its constituent primes? We will investigate these questions, and even stray into other rings when it makes sense to do so.

This is more than an academic exercise. These questions are a matter of national and international security. To see why, have a look at rsa encryption.

In theory, the quantum computer can factor large numbers, but the engineering challenges associated with such a device remain daunting.

Trial Division

Given a number n, divide it by everything smaller than n, looking for factors. The smallest number dividing n is a prime factor of n, and if there are no such factors then n is prime. This is an algorithm that is easily understood by all, but it is grossly inefficient.

Since the smallest prime factor is bounded by sqrt(n), you only need divide n by numbers ≤ sqrt(n). And after you've tried 2, you need not divide by the even numbers, and after you've tried 3 you need not divide by the multiples of 3, and so on for the smaller primes. Even with these tweaks, the algorithm is still inefficient. If n is a 30 digit number you need to run 1015 multiprecision divisions, and that's not chump change.

Pseudoprime Test

The pseudoprime test quickly determines whether n is prime - most of the time. (This was described in another section.)

The disclaimer is there for two reasons. First, there are some numbers, known as carmichael numbers, that are composite, yet they satisfy xn-1 = 1 for every value of x coprime to n. Second, the test is probabilistic, and you could get unlucky. Perhaps 90% of the values of x would prove n is composite, but you keep selecting x from that 10%, where xn-1 = 1 mod n.

When an algorithm is probabilistic, we need to include some error bars, e.g. n is prime with a certain probability. This is somewhat unsatisfying in pure mathematics, which calls for rigorous proofs, but it is often sufficient for real world applications such as cryptography. If n is prime with probability 1-10-50, that's good enough; go ahead and use it as a cipher key. Of course the pseudoprime test can't give you this kind of assurance, even after many trials, because n could be a carmichael number; but other tests can.