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
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 recommends that
$|p-q| \geq \sqrt{N}2^{-100}$
for any key of bitlength $1024,\ 2048,\ 3072$ in order to address this kind of
threat.\\
%% it would be nice here to explain that this magic 2^100 is just about wonting
%% the most significant digits to be different.
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, if we
decompose $x^2 - y^2$ as difference of squares, then it is immediately clear
that $x+y \mid N \ \land \  x-y \mid N$, and that both are non-trivial
divisors.

\paragraph{Complexity} \cite{riesel} contains a detailed proof for the
complexity of this algorirthm, which is
$\bigO{\frac{(1-k)^2}{2k} \sqrt{N}} \;\;,  0 < k < 1$. We summarize it down
below here to better clarify the limits of this algorithm.

\begin{proof}
  Since, once we reach the final step $x_f$ it holds $N = pq = x_f^2 - y_f^2$,
  the number of steps required to reach the result is:
  \begin{align*}
    x_f - \sqrt{N} &= \frac{p + q}{2} - \sqrt{N} \\
                   &= \frac{p + \frac{N}{p}}{2} - \sqrt{N} \\
                   &= \frac{(\sqrt{N} - p)^2}{2p}
  \end{align*}
  If we finally suppose that $p = k\sqrt{N}, \; 0 < k < 1$, then the number of cycles
  becomes
  $\frac{(1-k)^2}{2k} \sqrt{N}$.
\end{proof}

\begin{remark}
  Note that, for the algorithm to be effective, the two primes must be
  ``really close'' to $\sqrt{N}$. As much as the lowest prime gets near to
  $1$, the ratio $\frac{(1-k)^2}{2k}$ becomes larger, until the actual magnitude
  of this factorization method approaches \bigO{N}.
\end{remark}

\section{An Implementation 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 efficiently
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 optimizations
aforementioned.

\paragraph{How to chose the upper limit?}  after having explained our interpretation
of NISTS' upperbound limit - the most significat bits story, we ;should report
some practical tets.

\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 \dsqrt{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}

At first glance we might be willing to split the entire interval
$\{ \ceil{\sqrt{N}}, \ldots, N-1 \}$ in equal parts, one assigned to per each
node. Hovever, this would not be any more efficient than the trial division
algorithm, and nevertheless it is woth noting that during each single iteration,
the computational complexity is dominated by the quare root $\dsqrt$ function,
which belongs to the class \bigO{\log^2 N}, as we saw in section
~\ref{sec:preq:sqrt}. Computing separatedly $x^2$ would add an overhead of the
same order of magnitude \bigO{\log^2 N}, and thus result in a complete waste of
resources.
%%% Local Variables:
%%% TeX-master: "question_authority.tex"
%%% End: