整数因子分解

  • 更新时间: 2018-02-06
  • 来源: 原创或网络
  • 浏览数: 35次
  • 字数: 55813
  • 发表评论

相对于素数判定来说,因子分解的实现就没办法达到那么快速了。因子分解至今仍没有类似于素数判定的多项式算法,这也成为了RSA公钥系统安全得以保障的基础。鉴于这两个问题的难度相差较大,在我们施行分解之前,最好是预先知道目标整数的确不是一个素数,否则很可能花费了很大力气只干了素数判定的活——杀鸡用牛刀了。

因子分解的分为一般方法和特殊方法两大类,通常倾向于先针对数的特殊性(例如整数因子分解,by 5lulu.com)使用特殊方法,如果目标数的形式不那么特殊,再尝试使用一般方法。当然,前者往往要比后者快上许多。

我们这里着重介绍因子分解的一般方法,且总是用整数因子分解,by 5lulu.com表示待分解的目标数。特殊方法可以以后视实际情况逐渐加入。

1 试除法

无论素数判定还是因子分解,试除法(Trial Division)都是首先要进行的步骤。在试除的策略上有两种不同的选择:

  • 用足够大的空间来储存试除用的素数因子(储存方法可以相当紧凑,比如用整数因子分解,by 5lulu.com对应的0-1向量表示的大整数)。
  • 不耗费大量空间来储存所有需要的素因子,这时需要一个快速生成素数的子程序,或者干脆只用2,3以及整数因子分解,by 5lulu.com型的整数来作为试除因子。

很少发生一个数没有小因子的情况,例如根据Mertens定理[1],奇数中没有以下因子的比例整数因子分解,by 5lulu.com

可以知道76%的奇数都有小于100的素因子,而没有小于整数因子分解,by 5lulu.com因子的奇数比例仅为6.1%[2]。因此在大多数情况,试除法的第二种选择已经足够,实现却是最为简单的。

2 Euclid算法

Euclid算法用于因子分解也非常简单。我们预先计算好小于100的素数之积整数因子分解,by 5lulu.com

然后将与目标数进行Euclid算法,最终得到的最大公因子,继续分解公因子就可以得到在100以下的因子分解了。同样可以预先计算出100到200,200到300的素数乘积,等等。这本质上是试除法的一个实现,当非常大时,必须借助高精度算术来进行除以整数因子分解,by 5lulu.com的操作,因此频繁的试除会十分耗时,而Euclid方法可以施行很少次数,再在机器精度上完成最终的分解,提高效率。

3 Pollard 整数因子分解,by 5lulu.com 方法

Pollard 方法由Pollard于1974年提出,其基本想法是这样的:设素数,由Fermat小定理,又有,因此就可能是的一个非平凡因子。当然,问题在于我们并不知道是多少。一个合理的假设是的因子都很小,比如说,所有素因子都包含在因子基中,我们来尝试着找到一个能够“覆盖”,即是说,从而,因此我们可以转而求来获得所要的非平凡因子。例如设素因子上限为,便可以简单的取或是最小公倍数整数因子分解,by 5lulu.com.

下面给出Pollard 整数因子分解,by 5lulu.com方法的一个版本:

算法1(Pollard 整数因子分解,by 5lulu.com 方法)
  1. 设素因子搜索的上限为,生成以下的形如数对应的素数因子之表整数因子分解,by 5lulu.com,即:2,3,2,5,7,2,3,11,13,2...
  2. 随机选择正整数,顺次计算 整数因子分解,by 5lulu.com
  3. 定期检查(例如每当为20的倍数时),若,则得到一个整数因子分解,by 5lulu.com的因子;否则继续第2步中的递推计算。
注1 由于越小素数在分解中出现的幂次可能越高,中小素数(例如2,3)应当较多重复出现,第1步中的生成方法便考虑到了这一点,(实际上最终计算了整数因子分解,by 5lulu.com
注2 在极少的情形,也可能出现,即所有的素因子都同时出现在了之中,这时可以重新选取定期检查的时机或者换一个整数因子分解,by 5lulu.com进行计算。
注3 另一种类似的Williams 方法依赖于只有小的因子,著名的Lucas序列替代了这里的的幂次,乘法群(的二次非剩余)代替了乘法群。因此Pollard 方法与Williams 方法的关系就好像素数检测中的Lehmer 检测与Lucas 整数因子分解,by 5lulu.com检测的关系一样。具体可参看[3].
注4 实践中一般取整数因子分解,by 5lulu.com左右。
注5 Pollard 方法的时间复杂度为,其中整数因子分解,by 5lulu.com为一个正数[4]

4 Pollard 整数因子分解,by 5lulu.com 方法

目前几乎所有实用的分解方法都是概率性的算法,目标是找到能计算的算法,使得的概率较大(而最大公因子可以很快地计算)。上面的Pollard 就是一例,下面即将看到的Pollard 整数因子分解,by 5lulu.com方法也不例外。

Pollard 方法由Pollard在1975年提出,它来自一个有趣的事实:随机选取大约个整数(为一个常数),就有很大概率在这些整数中找到两个是同余的。实践中可以采用同余递推序列整数因子分解,by 5lulu.com

来产生伪随机数,其中为映射:。设的一个因子,且找到,则计算便可能得到整数因子分解,by 5lulu.com的一个非平凡因子。

整数因子分解,by 5lulu.com
Pollard $\rho$ 方法

的有限性,如上定义的一阶的递推序列意义下必定是最终循环的(如图,看上去就像希腊字母)。设其开头的非循环部分长度为,循环节长度为。著名的Floyd算法可以在整数因子分解,by 5lulu.com步内高效地找出序列中的两个重复元素,并且只用常数的储存空间。

算法2(Floyd)
  1. 依次判断是否整数因子分解,by 5lulu.com
  2. 若相等,则终止;否则继续第1步。
证明(算法的有效性) 只需证明必定存在满足$m<i\le m+l$。由于等价于,因此取的倍数即可。算法过程中不必保存所有,可以存下当前的并递推计算整数因子分解,by 5lulu.com

实践中常采用的整数因子分解,by 5lulu.com

选择二次的递推序列一方面能提供足够的随机性,另一方面计算起来也非常简便。

算法3(Pollard 整数因子分解,by 5lulu.com)
  1. 随机选取整数因子分解,by 5lulu.com
  2. 顺次计算整数因子分解,by 5lulu.com
  3. 计算整数因子分解,by 5lulu.com
  4. 每隔一段时间(例如),检测整数因子分解,by 5lulu.com,若非平凡则算法终止,否则继续第2步。
注6较大时,对每个都去检测可能会耗费大量时间,因为我们的目标只是得到的非平凡因子,可以通过计算,再定时检测整数因子分解,by 5lulu.com来减少计算次数。
注7 如同Pollard 方法,也可能出现计算出来的最大公因子,这时可改变检测间隔或干脆改变整数因子分解,by 5lulu.com重新进行计算。
注8 Pollard 方法的时间复杂度为整数因子分解,by 5lulu.com[4]。 实际上复杂度依赖于的最小素因子,在分离整数因子分解,by 5lulu.com的小因子时尤其有效。
注9 1980年,Brent[5]给出了Pollard 方法的一个改进,在分解整数时,该方法平均能够加速24%。这个改进是针对Floyd的算法2的,因为Floyd算法中,往往要重复计算整数因子分解,by 5lulu.com等,Brent有如下改进,无需重复计算,但仍能同样有效的找出重复元素,并且只要常数的储存空间。
算法4(Brent的改进)
  1. , ,若整数因子分解,by 5lulu.com,则算法终止。
  2. 为2的幂,即,令, 依次令,判断是否有整数因子分解,by 5lulu.com,若相等则算法终止。
证明(算法的有效性) 注意算法过程中整数因子分解,by 5lulu.com能够依次遍历所有正整数,重复算法2的论证可知。

5 平方型分解(SQUFOF)

平方型分解(SQUare FOrm Factorization)是由Shanks在大约三十前发展的算法,但他从来没有正式发表过[6]。尽管SQUFOF复杂度为也是一个指数级的算法(而下面介绍的CFRAC, ECM, QS等都是次指数级的),但其仍有自身的优势:一方面算法十分简洁优美、便于实现(甚至可以在袖珍计算器上实现),并且在整数因子分解,by 5lulu.com范围的整数分解仍然是最快的。

SQUFOF依赖于对二次域结构的分析,我们在这里仅给出算法的描述,略去证明,具体可参见[6]

算法5(SQUFOF)非平方数,非素数,一下算法输出整数因子分解,by 5lulu.com的一个非平凡因子。
  1. 整数因子分解,by 5lulu.com
  2. 顺次计算,直到为完全平方数。(整数因子分解,by 5lulu.com)
  3. 计算整数因子分解,by 5lulu.com
  4. 重复第二步中的计算,直到,输出整数因子分解,by 5lulu.com

6 连分式方法(CFRAC)

连分式方法(Continued FRACtion)是由Morrison和Brillhart于1975年提出的[7],他们运用此方法成功地分解了Fermat数。它以及之后要介绍的二次筛(QS)以及数域筛(NFS)都基于如下一个简单的事实:如果整数因子分解,by 5lulu.com

就是整数因子分解,by 5lulu.com的一个非平凡因子。

当然,寻找这样的不能只靠运气,CFRAC方法构造一组同余式 整数因子分解,by 5lulu.com

其中都是因子基中较小的素数。如果找到足够多这样的同余式(例如个数),那么利用二元域上的Gauss消元法,可以找到组合系数使得整数因子分解,by 5lulu.com

我们记整数因子分解,by 5lulu.com

此时若令 整数因子分解,by 5lulu.com

便则有我们所需要的整数因子分解,by 5lulu.com

如何构造这么多同余式呢?我们知道用连分式部分展式可以得到二次无理数()的好的有理数逼近。设为其近似分数,那么的绝对值就很小,从而很可能在因子基下分解,同时整数因子分解,by 5lulu.com,便能得到我们所期望的同余式(1)。

算法6(CFRAC方法)
  1. 选择适当的(通常取为1,当连分式展式周期太小而无法产生足够的同余式时选择另一个),令,使得整数因子分解,by 5lulu.com
  2. 计算的连分式展式,得到一系列近似分式整数因子分解,by 5lulu.com
  3. 计算,尝试在下得到的分解,若分解成功则有整数因子分解,by 5lulu.com
  4. 当得到足够多的同余式时(即可),用上的Gauss消元法得到(2)中的整数因子分解,by 5lulu.com
  5. ,输出的非平凡因子整数因子分解,by 5lulu.com
注10 由于,因此若,必有,因此必定为模的平方数,从而第一步中可以只选择限定条件的素数整数因子分解,by 5lulu.com
注11 连分式的计算可以只用简单的四则运算,Gauss消元法可以用一些稀疏矩阵的专用算法来加速,因此CFRAC最花时间的部分在的分解上,当分解整数因子分解,by 5lulu.com花去太久时间时可以直接放弃,转而求下一个同余式。
注12 CFRAC方法的时间复杂度为(见[4]),其中记号如下定义: 整数因子分解,by 5lulu.com
注13 寻找同余式(1)来进行分解的想法首先来自Dixon[8],他当时的做法是直接随机地选取,然后在下分解,算法复杂度为整数因子分解,by 5lulu.com,这也是第一个次指数阶的一般整数分解方法。

7 Lenstra椭圆曲线方法(ECM)

因子分解说到底就是寻找,使得非平凡,关键在于提高寻找的的成功率。Pollard 方法通过计算来提高成功率,实质上是在群中考虑问题。椭圆曲线方法(Elliptic Curve Method)转而在有限域上随机的椭圆曲线群中考虑问题。由于椭圆曲线可以有许多不同的选择,ECM方法要比Pollard 整数因子分解,by 5lulu.com高效许多,到目前为止是第三快的因子分解方法,仅次于数域筛和二次筛。

首先我们给出域上椭圆曲线的定义:

定义1(域上的椭圆曲线)是特征不为2,3的域,无平方因子,表示无穷远点,则整数因子分解,by 5lulu.com

称为整数因子分解,by 5lulu.com上的一条椭圆曲线。

注14 无平方因子等价于判别式整数因子分解,by 5lulu.com,即椭圆曲线是非奇异的,在几何上看没有“尖点”。

椭圆曲线既是代数曲线又是一个加法群:

定义2(椭圆曲线上的加法运算)为一椭圆曲线,,过的直线交于三点表示关于整数因子分解,by 5lulu.com轴的对称点。

定义加法

整数因子分解,by 5lulu.com

另有三种特殊约定:

  1. ,则直线视为整数因子分解,by 5lulu.com处的切线;
  2. ,则定义为无穷远点整数因子分解,by 5lulu.com
  3. ,则定义整数因子分解,by 5lulu.com
整数因子分解,by 5lulu.com
椭圆曲线

由定义通过简单的计算我们可以得到:

命题1(加法的显式表达),则 整数因子分解,by 5lulu.com

其中 整数因子分解,by 5lulu.com

注15 可以知道以上加法定义确实使整数因子分解,by 5lulu.com成为了一个加法交换群(尽管结合性的验证需要一些繁琐的计算)。

上面我们考虑了域上的椭圆曲线,然而对于因子分解的任务来说,我们需要考虑上的椭圆曲线。由于等在中未必可逆,此时上面的加法运算未必能定义好,不过这无关紧要,例如当不可逆时,我们已经可以通过计算来得到的非平凡因子,从而直接完成分解的目标;而当可逆时,一切可以正常按照上面的显式表达进行运算。因此在这里我们不再花功夫用严格的语言来定义整数因子分解,by 5lulu.com上的椭圆曲线了。

下面我们将Pollard 整数因子分解,by 5lulu.com中类似的想法用在椭圆曲线中。

定义3(整数的光滑性) 整数称为是-光滑,若其最大素因子整数因子分解,by 5lulu.com

Pollard 方法的实质就是期望整数足够光滑而能在因子基下分解。和Pollard 方法中的想法类似,ECM中首先从椭圆曲线中随机取一点,我们期望的阶是足够光滑的,从而可以在下分解,然后通过加法规则计算(当然我们预先并不知道),利用计算过程中出现的不可逆元,求得整数因子分解,by 5lulu.com的一个因子。

算法7(Lenstra ECM)为给定的搜索极限,整数因子分解,by 5lulu.com以下的所有素数。
  1. 随机选取整数为曲线整数因子分解,by 5lulu.com
  2. ,根据式(3)递推地计算。若计算过程中出现不可逆元整数因子分解,by 5lulu.com,则到第三步,否则到第一步。
  3. 计算。如果则输出,算法终止;如果整数因子分解,by 5lulu.com则到第一步。

下面我们谈一下搜索极限的取法,和Pollard 方法中一样,我们需要知道有限域上群的阶,下面有限域上椭圆曲线最主要的定理归功于Hasse,告诉我们群的阶在整数因子分解,by 5lulu.com左右[9]

定理1(Hasse)为一有限域上的椭圆曲线,则,其中整数因子分解,by 5lulu.com

下面的定理则给出了关于光滑性的一个估计[9]

定理2(Canfield-Erdős-Pomerance)整数因子分解,by 5lulu.com

其中表示的最大素因子,再设整数因子分解,by 5lulu.com

则有估计整数因子分解,by 5lulu.com

其中整数因子分解,by 5lulu.com为正实数。

由上面两个定理我们可以得到选取的一些信息,设素数,而,由定理1和2知道平均要试条曲线可以得到一个阶为-光滑的椭圆曲线,算法7计算总共需要个群运算,为使运算量最小,因此可取。实践中的选择依赖于时间的承受限度,例如我们将搜索的素数因子限制在以下,那么可取(接近整数因子分解,by 5lulu.com)。

由上面的讨论可以看出,ECM的时间复杂度依赖于的最小素因子而非本身(为),因此很适宜在试除法和Pollard 整数因子分解,by 5lulu.com方法之后用ECM来找出较小的因子(10-20个十进制位左右)。

ECM算法的效率很大程度取决于群运算的快慢,最关键的是模整数因子分解,by 5lulu.com的求逆运算。我们在本节最后给出Montgomery的一个加速算法,使得我们能够同时对多条椭圆曲线进行求逆运算。

算法8(Montgomery)为不能被整除的整数,本算法求出其逆或给出整数因子分解,by 5lulu.com的一个非平凡因子。
  1. 递推计算 整数因子分解,by 5lulu.com
  2. 施行一次扩展Euclid算法求出满足整数因子分解,by 5lulu.com
    • ,则整数因子分解,by 5lulu.com均有逆,到第三步;
    • ,依次计算直到,输出整数因子分解,by 5lulu.com的一个非平凡因子。
  3. 递推计算逆并输出: 整数因子分解,by 5lulu.com

8 二次筛法(QS)

二次筛法(Quadratic Seive)是由Pomerance于1981年提出的,直到1993年是世界上渐进最快的通用大整数因子分解方法,第一的位置后来被数域筛所取代,不过对于120位以下的整数,二次筛还是要比数域筛快一些。

单个多项式二次筛法(SPQS)

正如我们在CFRAC方法中提到的,QS方法也要构造一组同余式(1),但通过筛法避免了其中在因子基下的分解,而这种分解在不存在的情况下常常会大量消耗时间。设,若,则不难验证对于任意,也有。于是我们找到了一系列数都有因子整数因子分解,by 5lulu.com,这样一个事实构成了QS方法的基础。

我们取,为了使其与某个同余,且尽可能小以便在下分解,考虑二次多项式,则的阶,符合我们的要求。接下来是筛法的过程:对于中满足搜索极限的素数及幂次,首先求解方程,其解数(如果有解的话) 整数因子分解,by 5lulu.com

并且解都可以快速地求得。对方程的任一个解,令,则有。给定一个搜索区间(通常很长),则对任意与的整数倍的都有因子。可用一张表储存区间中每个整数对应的因子,当对所有进行如上过程后,通过检查表,即可得到许多中在整数因子分解,by 5lulu.com下完全分解的整数了。接下来的步骤则与CFRAC的后半部分完全相同。

注16 实践过程中可以构造这样一张表,若,则对应的表项增加(这可预先计算),最后检查表项若接近,即可知道整数因子分解,by 5lulu.com可完全分解,此处的对数函数的计算可以不那么精确,只要绝对误差在1以下即可。
注17 在一些启发性假设下,利用Canfield-Erdős-Pomerance的定理2,可以知道QS的时间复杂度为,与ECM差不多。但由于筛法的运用,QS的运算更简单一些,实践中要快于ECM,除非是在整数因子分解,by 5lulu.com较小的情形。

多个多项式二次筛法(MPQS)

MPQS是对上述只用一个二次多项式的SPQS方法的一个改进,使用更多的二次多项式来减小的值,从而减小的大小和搜索区间的长度。考虑形式的多项式(),配方得,因此可选取系数使,设,则。我们需要尽可能的小,设搜索区间的长度,自然的把的中心设置在的极小点整数因子分解,by 5lulu.com处,此时

整数因子分解,by 5lulu.com

上的最大值与最小值之差为整数因子分解,by 5lulu.com

从而宜取,且接近整数因子分解,by 5lulu.com。因此选择系数的过程可以如下进行

  1. 选择区间长度整数因子分解,by 5lulu.com
  2. 选择接近于的素数整数因子分解,by 5lulu.com
  3. 求解整数因子分解,by 5lulu.com(例如利用Shanks算法3)。
  4. 整数因子分解,by 5lulu.com

接下来的步骤便是对这样选取的多个多项式进行筛法,最终得到足够多的同余式进行整数因子分解,by 5lulu.com上的Gauss消元法。

注18 MPQS的过程明显有着并行化的特性。

9 数域筛法(NFS)

数域筛法(Number Field Sieve)是目前渐进最快的通用因子分解方法,其时间复杂度为,其中常数依赖于不同的算法实现。例如对于针对形式整数的特殊数域筛法(SNFS)有,而对于一般数域筛法(GNFS)有整数因子分解,by 5lulu.com。对于120位以上的大数,NFS是最强有力的分解算法。例如互联网上的分布式大整数分解项目NFSNet采用的便是此法。

参考文献

[1]Mendès France M. and Tenenbaum G.著 姚家燕 译, 素数论, 清华大学出版社, 北京, 2007.

[2]Hans Riesel, Prime Numbers and Computer Methods for Factorization, Boston; Basel; Stuttgart: Birkhäuser, 1985.

[3]H. C. Williams, A $p+1$ Method of Factoring, Mathematics of Computation 39 (1982), no.159, 225-234.

[4]Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, 2002.

[5]Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT Numerical Mathematics 20 (1980), no.2, 176--194.

[6]Jason E. Gower and Samuel S. Wagstaff, JR., Square form factorization, Mathematics of computation 77 (2008), no.261, 551-588.

[7]Michael A. Morrison and John Brillhart, A Method of Factoring and the Factorization of $F_7$, Mathematics of Computation 29 (1975), no.129, 183-205.

[8]John D. Dixon, Asymptotically Fast Factorization of Integers, Mathematics of Computation 36 (1981), no.153, 255-260.

[9]Henri Cohen, A Course in Computational Algebraic Number Theory, Springer Verlag, 1993.

我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议