\chapter{Fermat's Factorization Algorithm \label{chap:fermat}} Excluding the trial division, Fermat's method is the oldest known systematic method for factorizing integers. Even if its algorithmic complexity is not really among the most efficient, it holds still a practical interest whenever the two primes are sufficiently close. Indeed, \cite{DSS2009} \S B.3.6 explicitly reccomends that $|p-q| \geq \sqrt{N}2^{-100}$, in order to address this kind of threat, for any key of bitlength $1024,\ 2048,\ 3072$.\\ The basic idea is to attempt to write $N$ as a difference of squares, \begin{align} \label{eq:fermat_problem} x^2 - N = y^2 \end{align} So, we start by $x = \ceil{\sqrt{N}}$ and check that $x^2-N$ is a perfect square. If it isn't, we iterativelly increment $x$ and check again, until we find a pair $\angular{x, y}$ satisfying equation \ref{eq:fermat_problem}. Once found, we claim that $N = pq = (x+y)(x-y)$; it is indeed true that: \begin{proof} \label{proof:fermat} \begin{align*} x^2 - N = y^2 \\ x^2 - y^2 = N \\ (x+y)(x-y) = N \\ x+y \mid N \ \land \ x-y \mid N \end{align*} \end{proof} As it is straightforward to see, the order of magnitude of this algorithm is $\bigO{\sqrt{N}}$. \section{An Implementative Perspective} At each iteration, the $i-$th state is hold by the pair $\angular{x, x^2}$.\\ The later step, described by $\angular{x+1, (x+1)^2}$ can be computed efficently considering the square of a binomial: $\angular{x+1, (x^2) + (x \ll 1) + 1}$. The upperbound, instead, is reached when $ \Delta = p - q = x + y - x + y = 2y > 2^{-100}\sqrt{N}$. Algorithm ~\ref{alg:fermat} presents a simple implementation of this factorization method, taking into account the small aptimizations aforementioned. \begin{algorithm} \caption{Fermat Factorization \label{alg:fermat}} \begin{algorithmic}[1] \State $x \gets \floor{\sqrt{N}}$ \State $x^2 \gets xx$ \Repeat \State $x \gets x+1$ \State $x^2 \gets x^2 + x \ll 1 + 1$ \State $y, rest \gets sqrt(x^2 - N)$ \Until{ $rest \neq 0 \land y < \frac{\sqrt{N}}{2^{101}}$ } \If{ $rest = 0$ } \State $p \gets x+y$ \State $q \gets x-y$ \State \Return $p, q$ \Else \State \Return \textbf{nil} \EndIf \end{algorithmic} \end{algorithm} \section{Thoughts about parallelization} During each single iteration, the computational complexity is dominated by the quare root's $sqrt()$ function, which belongs to the class \bigO{lg^2 N}, as we saw in section ~\ref{sec:preq:sqrt}. Even if at first sight might seem plausible to split As we saw in Chapter ~\ref{chap:preq}, th %%% Local Variables: %%% TeX-master: "question_authority.tex" %%% End: