Fourth Week...

Hello everybody!

I recently passed an essay on Information Security and in this post I would also like to talk about one of the algorithms used, namely Fermat’s method for factorization.

In 1643, Pierre de Fermat proposed a factorization method. He noticed that a composite number can always be represented as the difference of two squares and, based on this observation, proposed a simple method for finding divisors.

Let $n = a \cdot b$, where $a$ and $b$ are natural, not necessarily prime, divisors of the number $n$ and $a>b$. Then $n=x^2-y^2$, where $x=\frac{a+b}{2}$, $y=\frac{a-b}{2}$.

Fermat’s method of factorization consists of going through all possible values of $x$ and checking whether the number $n-x^2$ is a perfect square. If this condition is met, then the divisors a and b satisfy the equalities $a=(x+y)$ and $b=(x-y)$.

The method boils down to trying to find two integers a and b that are close to each other $(a \approx b)$. The search starts with the smallest integer greater than $x=\sqrt{n}$. Next, we try to find another integer $y$, such that the equation $y^2=x^2-n$ is satisfied. At each iteration, you need to consider whether the result $x^2-n$ is a perfect square. If such a value is found for y, then $a$ and $b$ are calculated and the loop is exited. Otherwise, another iteration is carried out.

Algorithm.

Input: Odd composite integer $n>0$.

Output: Natural divisor $a>1$ of $n$.

1. Calculate the smallest integer $h$ such that $h \geq \sqrt{n}$, that is, $h=\lceil \sqrt{n} \rceil$.
2. If $h^2=n$, then determine $a=h$ and complete the algorithm.
3. Define $x \gets h, v=x^2-n$ and counter $k=0$.
4. If the value $v$ is a perfect square, then determine $y=\sqrt{v}, a=x+y$ and finish the algorithm.
5. Calculate $k \gets k+1, x \gets x+1$ and $v \gets x^2-n$. Return to point 4.

Note: the number of checks of the number $v$ (the number of repetitions at the fourth step of the algorithm) does not exceed the value $y=\frac{a-b}{2}$.

It is worth noting that this method does not necessarily find the prime factorization (canonical factorization), in which case the algorithm must be repeated recursively for each of the values $a$ and $b$ until the prime factors are found.

Fermat’s method can be applied to the public key cryptographic algorithm RSA, which relies on the computational complexity of the problem of factoring large semiprimes.

I hope you found this information useful. Have a great week!