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

许多分解因子算法的理论依据是这样的事实&＃xff1a;

假设我们可以找到$x\not\equiv \pm y(\mathrm{m}\mathrm{o}\mathrm{d}n)$&＃xff0c;但是有x2≡y2(modn)x^{2}\equiv y^{2}\pmod{n}x2≡y2(modn)。那么有
$$n|(x-y)(x\&＃43;y)$$
但是$n\nmid (x\&＃43;y)$且$n\nmid (x-y)$&＃xff0c;所以$gcd(x\&＃43;y,n)$和$gcd(x-y,n)$都是$n$的非平凡因子。

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

算法思想

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

1. 假设我们事先找到一个集合$B$称为因子基&＃xff0c;$B$中包含了$b$个最小的素数&＃xff08;$b$是适当选取的一个数&＃xff09;&＃xff1b;
2. 我们通过某种方法得到了若干个整数$z$&＃xff0c;使得z2modnz^{2}\mod{n}z2modn的所有因子都在集合$B$中&＃xff1b;
3. 将某些$z$相乘使得因子基中的每个素数出现偶数次&＃xff0c;这样就可以得到一个x2≡y2(modn)x^{2}\equiv y^{2}\pmod{n}x2≡y2(modn)的式子&＃xff0c;根据这个式子可以得到$n$的一个分解

通过例子看看具体的流程&＃xff1a;

设$n\&＃61;15770708441$&＃xff0c;并且取的$b\&＃61;6$&＃xff0c;那么$B\&＃61;\{1,3,5,7,11,13\}$&＃xff0c;找到三个$z$确定出如下三个方程&＃xff1a;
83409341562≡3×7(modn)120449429442≡2×7×13(modn)27737000112≡2×3×13(modn)8340934156^{2} \equiv 3\times 7\pmod{n}\\ 12044942944^{2} \equiv 2\times 7\times 13\pmod{n}\\ 2773700011^{2} \equiv 2\times 3 \times 13\pmod{n} 83409341562≡3×7(modn)120449429442≡2×7×13(modn)27737000112≡2×3×13(modn)
把上式两边同时相乘得到
(8340934156×12044942944×2773700011)2≡(2×3×7×13)2(modn)(8340934156\times 12044942944 \times 2773700011)^{2} \equiv (2\times 3\times 7\times 13)^{2}\pmod{n} (8340934156×12044942944×2773700011)2≡(2×3×7×13)2(modn)
即
95034357852≡5462(modn)9503435785^{2} \equiv 546^{2}\pmod{n} 95034357852≡5462(modn)
利用Euclidean算法&＃xff0c;计算
$$gcd(9503435785-546,n)\&＃61;115759$$
所以得到$n$的一个因子为115759.

几个关键问题

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

   这里没有完全绝对的方法&＃xff0c;只能给出几个技巧。一种技巧是简单地随机选择一些$z$&＃xff0c;计算z2modnz^{2}\bmod{n}z2modn&＃xff0c;这也是随机平方法名字的由来&＃xff1b;二是使用行如j&＃43;⌈kn⌉,j&＃61;0,1,2,⋯,k&＃61;1,2,⋯j&＃43;\lceil \sqrt{kn} \rceil,j&＃61;0,1,2,\cdots,k&＃61;1,2,\cdotsj&＃43;⌈kn

   ​⌉,j&＃61;0,1,2,⋯,k&＃61;1,2,⋯&＃xff0c;这些整数的平方模$n$之后&＃xff0c;通常很小&＃xff0c;因子容易落在$B$中&＃xff1b;另外可以使用行如⌊kn⌋\lfloor \sqrt{kn} \rfloor⌊kn

   ​⌋的整数&＃xff0c;这些数在模$n$之后&＃xff0c;比$n$小一点&＃xff0c;这意味着−z2-z^{2}−z2是很小的&＃xff0c;只要我们把-1加入$B$中&＃xff0c;就可以容易地在$B$上分解z2z^{2}z2。

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

   假定B&＃61;{p1,⋯,pb}B&＃61;\lbrace p_{1},\cdots,p_{b}\rbraceB&＃61;{p1​,⋯,pb​}为因子基。设$c$为稍大于$b$的整数&＃xff08;比如$c\&＃61;b\&＃43;1$&＃xff0c;$c\&＃61;b\&＃43;2$&＃xff09;&＃xff0c;且假定我们已经得到$c$个同余方程&＃xff1a;
   zj2≡p1α1j×p2α2j×⋯×pbαbj(modn)z_{j}^{2}\equiv p_{1}^{\alpha_{1j}} \times p_{2}^{\alpha_{2j}} \times \cdots \times p_{b}^{\alpha_{bj}}\pmod{n} zj2​≡p1α1j​​×p2α2j​​×⋯×pbαbj​​(modn)
   其中$1\le j\le c$。对于每个$j$&＃xff0c;考虑向量
   αj&＃61;(α1jmod2,⋯,αbjmod2)∈(Z2)b\alpha _{j} &＃61;(\alpha_{1j}\bmod{2},\cdots,\alpha_{bj}\bmod{2})\in (\mathbb{Z}_{2})^{b} αj​&＃61;(α1j​mod2,⋯,αbj​mod2)∈(Z2​)b
   如果我们可以找到{aj}\lbrace a_{j}\rbrace{aj​}的子集使得其模2的和为向量$\{0,0,\cdots ,0\}$&＃xff0c;那么对应的zjz_{j}zj​的乘积将会使用$B$中每个因子偶数次。

例子

3. $B$该怎么选。

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