| 123456789101112131415161718192021222324 |
- \chapter{Dixon \label{chap:dixon}}
- ~\cite{dixon} describes a class of ``probabilistic algorithms'' for finding a
- factor of any composite number, 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$.
- \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$ -recall Fermat's
- problem, formulated in equation ~\ref{eq:fermat_problem}, 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,
- %%% Local Variables:
- %%% mode: latex
- %%% TeX-master: "question_authority"
- %%% End:
|
