Introduction to Cryptography with Coding Theory, 3rd Edition

9.4 Factoring

We now turn to factoring. The basic method of dividing an integer $n$ by all primes $p\le \sqrt{n}$ is much too slow for most purposes. For many years, people have worked on developing more efficient algorithms. We present some of them here. In Chapter 21, we’ll also cover a method using elliptic curves, and in Chapter 25, we’ll show how a quantum computer, if built, could factor efficiently.

One method, which is also too slow, is usually called the Fermat factorization method. The idea is to express $n$ as a difference of two squares: $n=x^2-y^2$. Then $n=(x+y)(x-y)$ gives a factorization of $n$. For example, suppose we want to factor $n=295927$. Compute $n+1^2$, $n+2^2$, $n+3^2$, $\dots$, until we find a square. In this case, $295927+3^2=295936={544}^2$. Therefore,

$$\mathrm{295927\; ...}$$