Programming Praxis

We have previously studied integer factorization by trial division and wheel factorization. In this exercise we will implement integer factorization by Fermat’s method. Pierre de Fermat was a French lawyer and amateur mathematician of the seventeenth century, a contemporary of René Descartes and Blaise Pascal, who did early work in calculus, number theory, analytic geometry and probability.

Fermat’s method works by noticing that if n, the odd number to be factored, can be written as the difference of two squares n = x² – y², then it can be factored as (x – y) × (x + y). Thus, to find the factors of n, we start with y = 0 and x as the smallest integer greater than or equal to the square root of n and increase y until x² – y² is equal to n, in which case x and y reveal the factors of n, or x² – y² is less than n, when we increase x by one and iterate. This process must terminate; if n is prime, it will stop with the factors 1 and n.

Though this method works, the repeated squarings are relatively expensive, so it is normal to work with u = 2x + 1 and v = 2y + 1 and to keep track of r = x² – y² – n; when r = 0, the algorithm terminates. The variable u keeps track of the amount r increases when x² is replaced by (x + 1)² and variable v keeps track of the amount r decreases when y is replaced by (y + 1)²; as x and y increase by 1, u and v increase by 2.

Your task is to implement integer factorization by Fermat’s method. When you are finished, you are welcome to read or run the suggested solution, or post your own solution or discuss the exercise in the comments below.

Pages: 1 2