大整数分解因子算法——Dixon的随机平方算法

许多分解因子算法的理论依据是这样的事实：

假设我们可以找到$x\not\equiv \pm y(\mathrm{m}\mathrm{o}\mathrm{d}n)$，但是有$x^2\equiv y^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$。那么有
$$n|(x-y)(x+y)$$
但是$n\nmid (x+y)$且$n\nmid (x-y)$，所以$gcd(x+y,n)$和$gcd(x-y,n)$都是$n$的非平凡因子。

Dixon的随机平方算法也是利用这个事实进行设计的。

算法思想

我们先描述出随机平方算法的大致全貌，再分点详细讨论细节问题。

1. 假设我们事先找到一个集合$B$称为因子基，$B$中包含了$b$个最小的素数（$b$是适当选取的一个数）；
2. 我们通过某种方法得到了若干个整数$z$，使得$z^2\mathrm{m}\mathrm{o}\mathrm{d}n$的所有因子都在集合$B$中；
3. 将某些$z$相乘使得因子基中的每个素数出现偶数次，这样就可以得到一个$x^2\equiv y^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$的式子，根据这个式子可以得到$n$的一个分解

通过例子看看具体的流程：

设$n=15770708441$，并且取的$b=6$，那么B={1,3,5,7,11,13}B=\lbrace 1,3,5,7,11,13\rbraceB={1,3,5,7,11,13}，找到三个$z$确定出如下三个方程：
$$\begin{gathered} 8340934156^2\equiv 3\times 7(\mathrm{m}\mathrm{o}\mathrm{d}n) \\ 12044942944^2\equiv 2\times 7\times 13(\mathrm{m}\mathrm{o}\mathrm{d}n) \\ 2773700011^2\equiv 2\times 3\times 13(\mathrm{m}\mathrm{o}\mathrm{d}n) \end{gathered}$$
把上式两边同时相乘得到
$$(8340934156\times 12044942944\times 2773700011{)}^2\equiv (2\times 3\times 7\times 13{)}^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$$
即
$$9503435785^2\equiv 546^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$$
利用Euclidean算法，计算
$$gcd(9503435785-546,n)=115759$$
所以得到$n$的一个因子为115759.

几个关键问题

1. 如何选择$z$才能使得$z^2\mathrm{m}\mathrm{o}\mathrm{d}n$的所有因子都在集合$B$中。

   这里没有完全绝对的方法，只能给出几个技巧。一种技巧是简单地随机选择一些$z$，计算$z^2\mathrm{m}\mathrm{o}\mathrm{d}n$，这也是随机平方法名字的由来；二是使用行如$j+\lceil \sqrt{kn}\rceil ,j=0,1,2,\cdots ,k=1,2,\cdots$，这些整数的平方模$n$之后，通常很小，因子容易落在$B$中；另外可以使用行如$\lfloor \sqrt{kn}\rfloor$的整数，这些数在模$n$之后，比$n$小一点，这意味着$-z^2$是很小的，只要我们把-1加入$B$中，就可以容易地在$B$上分解$z^2$。

2. 选择哪些$z$才能使得那些$z$相乘后，因子基中的每个素数出现偶数次。

   假定B={p1,⋯ ,pb}B=\lbrace p_{1},\cdots,p_{b}\rbraceB={p1​,⋯,pb​}为因子基。设$c$为稍大于$b$的整数（比如$c=b+1$，$c=b+2$），且假定我们已经得到$c$个同余方程：
   $$z_j^2\equiv p_1^{{\alpha }_{1j}}\times p_2^{{\alpha }_{2j}}\times \cdots \times p_b^{{\alpha }_{bj}}(\mathrm{m}\mathrm{o}\mathrm{d}n)$$
   其中$1\le j\le c$。对于每个$j$，考虑向量
   $${\alpha }_j=({\alpha }_{1j}\mathrm{m}\mathrm{o}\mathrm{d}2,\cdots ,{\alpha }_{bj}\mathrm{m}\mathrm{o}\mathrm{d}2)\in ({\mathbb{Z}}_2{)}^b$$
   如果我们可以找到{aj}\lbrace a_{j}\rbrace{aj​}的子集使得其模2的和为向量{0,0,⋯ ,0}\lbrace 0,0,\cdots,0\rbrace{0,0,⋯,0}，那么对应的$z_j$的乘积将会使用$B$中每个因子偶数次。

例子

3. $B$该怎么选。

$B$的选取比较复杂，如果$b=|B|$取得越大，整数$z^2$似乎更容易在$B$上分解。但是$b$越大，为了找到一个等式需要累积很多同余式。具体方法我们就不赘述，有兴趣的可以参考书籍——Stinson D , 斯廷森, 冯登国. 密码学原理与实践[M]. 电子工业出版社, 2009.