dixon.tex 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275
  1. \chapter{Dixon's factorization method\label{chap:dixon}}
  2. ~\cite{dixon} describes a class of ``probabilistic algorithms'' for finding a
  3. factor of any composite number, at a sub-exponential cost. They basically
  4. consists into taking random integers $r$ in $\{1, \ldots, N\}$ and look for those
  5. where $r^2 \mod{N}$ is \emph{smooth}. If enough are found, then those integers
  6. can somehow be assembled, and so a fatorization of N attemped.
  7. %% that's not really academic to be stated officially, but I would have never
  8. %% understood this section without Firas (thanks).
  9. %% <http://blog.fkraiem.org/2013/12/08/factoring-integers-dixons-algorithm/>
  10. %% I kept the voila` phrase, that was so lovely.
  11. \section{Interlude \label{sec:dixon:history}}
  12. During the latest century there has been a huge effort to approach the problem
  13. formulated by Fermat ~\ref{eq:fermat_problem} from different perspecives. This
  14. led to an entire family of algorithms, like \emph{Quadratic Sieve},
  15. \emph{Dixon}, \ldots.
  16. The core idea is still to find a pair of perfect squares whose difference can
  17. factorize $N$, but maybe Fermat's hypotesis can be made weaker.
  18. \paragraph{Kraitchick} was the first one popularizing the idea that instead of
  19. looking for integers $\angular{x, y}$ such that $x^2 -y^2 = N$ it is sufficient
  20. to look for \emph{multiples} of $N$:
  21. \begin{align}
  22. x^2 - y^2 \equiv 0 \pmod{N}
  23. \end{align}
  24. and, once found, claim that $\gcd(N, x \pm y)$ are non-trial divisors of $N$
  25. just as we did in \ref{sec:fermat:implementation}.
  26. Kraitchick did not stop here: instead of trying $x^2 \equiv y^2 \pmod{N}$ he
  27. kept the value of previous attempt, and tries to find \emph{a product} of such
  28. values which is also a square. So we have a sequence
  29. \begin{align}
  30. \label{eq:dixon:x_sequence}
  31. \angular{x_0, \ldots, x_k} \mid \forall i \leq k \quad x_i^2 - N
  32. \; \text{ is a perfect square}
  33. \end{align}
  34. and hence
  35. \begin{align*}
  36. \prod_i (x_i^2 - N) = y^2
  37. \end{align*}
  38. that $\mod{N}$ is equivalent to:
  39. \begin{align}
  40. \label{eq:dixon:fermat_revisited}
  41. y^2 \equiv \prod_i (x_i^2 - N) \equiv \big( \prod_i x_i \big) ^2 \pmod{N}
  42. \end{align}
  43. and voil\`a our congruence of squares (\cite{discretelogs} \S 4). For what
  44. concerns the generation of $x_i$ with the property \ref{eq:dixon:x_sequence},
  45. they can simply be taken at random and tested using trial division.
  46. \paragraph{Brillhart and Morrison} later proposed (\cite{morrison-brillhart}
  47. p.187) a better approach than trial division to find such $x$. Their idea aims
  48. to ease the enormous effort required by the trial division. In order to achieve
  49. this. they introduce a \emph{factor base} $\factorBase$ and generate random $x$
  50. such that $x^2 - N$ is $\factorBase$-smooth. Recalling what we anticipated in
  51. ~\ref{chap:preq}, $\factorBase$ is a precomputed set of primes
  52. $p_i \in \naturalPrime$.
  53. This way the complexity of generating a new $x$ is dominated by
  54. \bigO{|\factorBase|}. Now that the right side of \ref{eq:dixon:fermat_revisited}
  55. has been satisfied, we have to select a subset of those $x$ so that their
  56. product can be seen as a square. Consider an \emph{exponent vector}
  57. $v_i = (\alpha_0, \alpha_1, \ldots, \alpha_r)$ with $r = |\factorBase|$
  58. associated with each $x_i$, where
  59. \begin{align}
  60. \label{eq:dixon:alphas}
  61. \alpha_j = \begin{cases}
  62. 1 \quad \text{if $p_j$ divides $x_i$ to an odd power} \\
  63. 0 \quad \text{otherwise}
  64. \end{cases}
  65. \end{align}
  66. for each $1 \leq j \leq r $. There is no need to restrict ourselves for positive
  67. values of $x^2 -N$, so we are going to use $\alpha_0$ to indicate the sign. This
  68. benefit has a neglegible cost: we have to add the non-prime $-1$ to our factor
  69. base $\factorBase$.
  70. Let now $M \in \mathbb{F}_2^{(f \times r)}$,
  71. for some $f \geq r$,
  72. be the rectangular matrix having per each $i$-th row the
  73. $v_i$ associated to $x_i$: this way each matrix element $m_{ij}$ will be the
  74. $j$-th component of $v_i$.
  75. We are interested in finding set(s) of the subsequences of $x_i$
  76. whose product always have even powers (\ref{eq:dixon:fermat_revisited}).
  77. Turns out that this is equivalent to look for the set of vectors
  78. $\{ w \mid wM = 0 \} = \ker(M)$ by definition of matrix multiplication
  79. in $\mathbb{F}_2$.
  80. \paragraph{Dixon} Morrison and Brillhart's ideas of \cite{morrison-brillhart}
  81. were actually used for a slightly different factorization method, employing
  82. continued fractions instead of the square difference polynomial. Dixon simply
  83. ported these to the square problem, achieving a probabilistic factorization
  84. method working at a computational cost asymptotically better than all other ones
  85. previously described: \bigO{\exp \{\beta(\log N \log \log N )^{\rfrac{1}{2}}\}}
  86. for some constant $\beta > 0$ \cite{dixon}.
  87. \section{Breaching the kernel}
  88. The following reduction procedure, extracted from ~\cite{morrison-brillhart}, is
  89. a forward part of the Gauss-Jordan elimination algorithm (carried out from right
  90. to left), and can be used to determine whether the set of exponent vectors is
  91. linearly dependent.
  92. For each $v_i$ described as above, associate a \emph{companion history vector}
  93. $h_i = (\beta_0, \beta_1, \ldots, \beta_f)$, where for $0 \leq m \leq f$:
  94. \begin{align*}
  95. \beta_m = \begin{cases}
  96. 1 \quad \text{ if $m = i$} \\
  97. 0 \quad \text{ otherwise}
  98. \end{cases}
  99. \end{align*}
  100. At this point, we have all data structures needed:
  101. \\
  102. \\
  103. \\
  104. \begin{center}
  105. \emph{Reduction Procedure}
  106. \end{center}
  107. \begin{enumerate}[(i)]
  108. \item Set $j=r$;
  109. \item find the ``pivot vector'', i.e. the first vector
  110. $e_i, \quad 0 \leq i \leq f$ such that $\alpha_j = 1$. If none is found, go
  111. to (iv);
  112. \item
  113. \begin{enumerate}[(a)]
  114. \item replace every following vector $e_m, \quad i < m \leq f$
  115. whose rightmost $1$ is the $j$-th component, by the sum $e_i \xor e_m$;
  116. \item whenever $e_m$ is replaced by $e_i \xor e_m$, replace also the
  117. associated history vector $h_m$ with $h_i \xor h_m$;
  118. \end{enumerate}
  119. \item Reduce $j$ by $1$. If $j \geq 0$, return to (ii); otherwise stop.
  120. \end{enumerate}
  121. Algorithm \ref{alg:dixon:kernel} formalizes concepts so far discussed, by
  122. presenting a function \texttt{ker}, discovering linear dependencies in any
  123. rectangular matrix $M \in \mathbb{F}_2^{(f \times r)}$
  124. and storing dependencies into a \emph{history matrix} $H$.
  125. \begin{remark}
  126. We are proceeding from right to left in order to conform with
  127. \cite{morrison-brillhart}.
  128. Instead, their choice lays on optimization reasons, which does
  129. not apply any more to a modern calculator.
  130. \end{remark}
  131. \begin{algorithm}
  132. \caption{Reduction Procedure \label{alg:dixon:kernel}}
  133. \begin{algorithmic}[1]
  134. \Function{Ker}{$M$}
  135. \State $H \gets \texttt{Id}(f \times f)$
  136. \Comment the initial $H$ is the identity matrix
  137. \For{$j = r \strong{ downto } 0$}
  138. \Comment reduce
  139. \For{$i=0 \strong{ to } f$}
  140. \If{$M_{i, j} = 1$}
  141. \For{$i' = i \strong{ to } f$}
  142. \If{$M_{i', k} = 1$}
  143. \State $M_{i'} = Mi \xor M_{i'}$
  144. \State $H_{i'} = H_i \xor H_{i'}$
  145. \EndIf
  146. \EndFor
  147. \State \strong{break}
  148. \EndIf
  149. \EndFor
  150. \EndFor
  151. \For{$i = 0 \strong{ to } f$}
  152. \Comment yield linear dependencies
  153. \If{$M_i = (0, \ldots, 0)$}
  154. \strong{yield} $\{\mu \mid H_{i,\mu} = 1\}$
  155. \EndIf
  156. \EndFor
  157. \EndFunction
  158. \end{algorithmic}
  159. \end{algorithm}
  160. \section{An Implementation Perspective}
  161. Before gluing all toghether, we need one last building brick necessary for
  162. Dixon's factorization algorithm: a \texttt{smooth}($x$) function. In our
  163. specific case, we need a function that, given as input a number $x$, returns the
  164. empty set $\emptyset$ if $x^2 -N$ is not $\factorBase$-smooth. Otherwise,
  165. returns a vector $v = (\alpha_0, \ldots, \alpha_r)$ such that each $\alpha_j$ is
  166. defined just as in \ref{eq:dixon:alphas}. Once we have established $\factorBase$, its
  167. implementation comes straightfoward.
  168. \paragraph{How do we choose $\factorBase$?}
  169. It's not easy to answer: if we choose $\factorBase$ small, we will rarely find
  170. $x^2 -N$ \emph{smooth}. If we chose it large, attempting to factorize $x^2 -N$
  171. with $\factorBase$ will pay the price of iterating through a large set.
  172. \cite{Crandall} \S 6.1 finds a solution for this employng complex analytic
  173. number theory. As a result, the ideal value for $|\factorBase|$ is
  174. $e^{\sqrt{\ln N \ln \ln N}}$.
  175. \begin{algorithm}
  176. \caption{Discovering Smoothness}
  177. \begin{algorithmic}[1]
  178. \Require $\factorBase$, the factor base
  179. \Procedure{smooth}{$x$}
  180. \State $v \gets (\alpha_0 = 0, \ldots, \alpha_{|\factorBase|} = 0)$
  181. \If{$x < 0$} $\alpha_0 \gets 1$ \EndIf
  182. \For{$i = 1 \strong{ to } |\factorBase|$}
  183. \If{$\factorBase_i \nmid x$} \strong{continue} \EndIf
  184. \State $x \gets x// \factorBase_i$
  185. \State $\alpha_i \gets \alpha_i \xor 1$
  186. \EndFor
  187. \If{$x = 1$}
  188. \State \Return $v$
  189. \Else
  190. \State \Return \strong{nil}
  191. \EndIf
  192. \EndProcedure
  193. \end{algorithmic}
  194. \end{algorithm}
  195. \begin{algorithm}
  196. \caption{Dixon}
  197. \begin{algorithmic}[1]
  198. \Require $\factorBase$, the factor base
  199. \Function{dixon}{\PKArg}
  200. \State $i \gets 0$
  201. \State $r \gets |\factorBase| + 5$
  202. \Comment finding linearity requires redundance
  203. \While{$i < r$}
  204. \Comment search for suitable pairs
  205. \State $x_i \getsRandom \naturalN_{< N}$
  206. \State $y_i \gets x_i^2 - N$
  207. \State $v_i \gets \textsc{smooth}(y_i)$
  208. \If{$v_i$} $i \gets i+1$ \EndIf
  209. \EndWhile
  210. \State $M \gets \texttt{matrix}(v_0, \ldots, v_f)$
  211. \For{$\lambda = \{\mu_0, \ldots, \mu_k\}
  212. \strong{ in } \textsc{ker}(M)$}
  213. \Comment get relations
  214. \State $x \gets \prod\limits_{\mu \in \lambda} x_\mu \pmod{N}$
  215. \State $y, r \gets \dsqrt{\prod\limits_{\mu \in \lambda} y_\mu \pmod{N}}$
  216. \If{$\gcd(x+y, N) > 1$}
  217. \State $p \gets \gcd(x+y, N)$
  218. \State $q \gets \gcd(x-y, N)$
  219. \State \Return $p, q$
  220. \EndIf
  221. \EndFor
  222. \EndFunction
  223. \end{algorithmic}
  224. \end{algorithm}
  225. \paragraph{Parallelism}
  226. Dixon's factorization is ideally suited to parallel implementation. Similarly to
  227. other methods like ECM and MPQS, treated in \cite{brent:parallel} \S 6.1,
  228. we can \emph{linearly} improve the running time by distributing across many
  229. nodes the discovery of $\factorBase$-smooth numbers.
  230. Depending on the granularity we desire - and the number of nodes available, we
  231. can even act on the \texttt{ker} function - but less easily.
  232. This idea would boil down to the same structure we discussed with Wiener's attack:
  233. one node - the \emph{producer} - discovers linear dependencies, while the others
  234. - the \emph{consumers} - attempt to factorize $N$.
  235. For this reason that we introduced the \texttt{yield} statement in line
  236. $12$ of algorithm \ref{alg:dixon:kernel}: the two jobs can be performed
  237. asynchronously.
  238. Certainly, due to the probabilistic nature of this algorithm, we can even think
  239. aboutrunning multiple instances of the same program. This solution is fairly
  240. effective in proportion to the development cost.
  241. %%% Local Variables:
  242. %%% mode: latex
  243. %%% TeX-master: "question_authority"
  244. %%% End: