bachelor/book/fermat.tex

\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: