bachelor/book/dixon.tex

\chapter{Dixon {\texttt{\small{[insert random buzzword here]}}} method\label{chap:dixon}}

~\cite{dixon} describes a class of ``probabilistic algorithms'' for finding a
factor of any composite number, at a sub-exponential cost. They basically
consists into taking random integers $r$ in $\{1, \ldots, N\}$ and look for those
where $r^2 \mod{N}$ is \emph{smooth}. If enough are found, then those integers
can somehow be assembled, and so a fatorization of N attemped.


\section{Quadratic Sieve}
During the latest century there has been a huge effort to approach the problem
formulated by Fermat ~\ref{eq:fermat_problem} from different perspecives. This
led to an entire family of algorithms known as \emph{Quadratic Sieve} [QS]. The
core idea is still to find a pair of perfect squares whose difference can
factorize $N$, but maybe Fermat's hypotesis can be made weaker.

\paragraph{Kraitchick} was the first one popularizing the idea the instead of
looking for integers $\angular{x, y}$ such that $x^2 -y^2 = N$ it is sufficient
to look for \emph{multiples} of $N$:
\begin{align}
  x^2 - y^2 \equiv 0 \pmod{N}
\end{align}
and, once found, claim that $\gcd(N, x \pm y)$ are non-trial divisors of $N$
just as we did in \ref{sec:fermat:implementation}.
On the top of this,

\section{stuff}

at a computational cost asymptotically  best
than all other ones previously described:
\bigO{\beta(\log N \log \log N)^{\rfrac{1}{2}}}
for some constant $\beta > 0$.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "question_authority"
%%% End: