整数分解方法探讨

yangchuanju

整数分解方法探讨
当前，在互联网上可以下载一些常用的分解软件，亦可在分解网站上查阅各类数字的分解情况，懒得自己亲自动手分解。
用着时用分解软件分解一些数据，或者在分解网站的相关网页中下载一点。
会编程的老师们，往往自己编程分解一些特定的整数；遗憾的是我不会编制分解程序。
整数分解方法有很多种，最基本的方法就是试除法；其次是费马平方差法、波拉德ρ法、波拉德p-1法、连分数法；
更专业的分解方法有二次筛法、椭圆曲线法等等。
近日闲的无聊，详细研究了《初等数论及其应用》（原书第5版中译本）中给出的波拉德ρ法、波拉德p-1法、连分数法分解方法，并按照数中所讲原理，分解了几个特定整数。
（更专业的二次筛法、椭圆曲线法上述数论书中没有介绍）

yangchuanju

分解大整数的方法有哪些
AI智能回答
分解大整数的方法包括试除法、Fermat算法（费马平方差法）、Pollard Rho算法（波拉德ρ法）、Pollard p - 1方法（波拉德p-1法）、平方整数分解方法和多项式分解方法。
试除法：也叫穷举法，是最简单和最容易理解的算法，但效率最低。它检查n的所有可能的因子，如果失败则证明n是个素数，因此常用来判断一个数是不是质数1。
Fermat算法：基于费马整数分解原理，通过寻找两个平方数的差来分解大整数。虽然效率不高，但比试除法要好很多。
Pollard Rho算法：利用多项式f(x)迭代出的值，通过Floyd判环算法来判断循环，从而找到大整数的一个因子。组合使用Pollard Rho算法与Miller Rabin算法，可求出大整数的所有因子。
Pollard p - 1方法：由Pollard于1974年提出，用来找到给定合数n的一个因子，是一种概率性算法。
平方整数分解方法：基于费马算法的延伸，巧妙利用Lasvegas算法逼近分解所需的平方数。
多项式分解方法：将大整数分解问题对应到一元高次多项式的分解问题上，其解决依赖于已有的多项式分解的理论。
以上方法各有优缺点，适用于不同情况下的大整数分解。在实际应用中，选择哪种方法取决于大整数的特性以及所需的计算效率。

yangchuanju

波拉德ρ法分解大整数
《初等数论及其应用》（原书第5版中译本）摘抄

4.6  利用波拉德ρ方法分解整数
在本书中，我们将描述一个基于同余的分解方法，它由J.M.波拉德(J.M.Polland)在1974年提出，J.M.波拉德称之为蒙特卡罗方法，
因为它依赖于生成貌似随机挑选的整数；现在称为波拉德ρ法，后面会解释为何这样命名。

设n是一个大合数，p是它的最小素因子。我们的目标是选取整数x0,x1,…,xi，使得它们有不同的模n最小非剩余，但它们模p的最小非负剩余不是全部不同的。
使用一些概率公式易证，在s与√p相比较大，而与√n相比较小，数字x1,x2,…,xi是随机地选取时，这是可能发生的。

一旦找到整数xi和xj，0≤i≤j≤s，满足xi≡xj(mod p)，且xi≡/≡xj(mod n)，则(xi-xj  n)是n的非平凡因子，这是因为p整除xi-xj，但n不整除xi-xj，可用欧几里得算法迅速求出(xi-xj  n)。
然而，对每对(xi,xj)，0≤i<j≤s，求(xi-xj,  n)，则共需要求O(s^2)个最大公因子，我们将说明如何减少必须使用的欧几里得算法的次数。

我们用下面的方法寻找这样的整数xi和xj，首先随机选取种子值x0，f(x)是次数大于1的整系数多项式，然后用递归定义
xk+1≡f(xk) (mod n)，0≤xk+1<n  {附注：k k+1都是x的下标）
计算xk，k=1,2,...，多项式f(x)的选取应该使得有很高概率在出现重复之前生成适当多的整数xi，经验表明，多项式f(x)=x^2+1在这一检验中表现良好，下面的例子说明了如何生成这样的序列。

yangchuanju

波拉德ρ法分解大整数                       
分解式        8051=97*83               
待分解数n        8051               
生成多项式f(x)        x^2+1        gcd(x2k-xk,n)        gcd(f(xi),p)
选取种子x0        2        ——        97
x1        5        ——        5
x2        26        1        26
x3        677        ——        95
x4        7474        1        5
x5        2839        ——        26
x6        871        97        95

x1=x0^2+1  (mod n)
x2=x1^2+1  (mod n)
……
x6=x5^2+1 (mod n)
下同，略

yangchuanju

波拉德ρ法分解大整数                       
分解式        1189=29*41               
待分解数n        1189        ——        ——
生成多项式f(x)        x^2+1        gcd(x2k-xk,n)        gcd(f(xi),p)       
选取种子x0        2        ——        29
x1        5        ——        5
x2        26        1        26
x3        677        ——        10
x4        565        1        14
x5        574        ——        23
x6        124        #NUM!        8
x7        1109        ——        7
x8        456        #NUM!        21
x9        1051        ——        7
x10        21        #NUM!        21
x11        442        ——        7
x12        369        1        21
x13        616        ——        7
x14        166        #NUM!        21
x15        210        ——        7
x16        108        #NUM!        21
x17        964        ——        7
x18        688        #NUM!        21
x19        123        ——        7
x20        862        29        21

yangchuanju

波拉德ρ法分解大整数                       
分解式        1927=47*41               
待分解数n        1927        ——        ——
生成多项式f(x)        x^2+1        gcd(x2k-xk,n)        gcd(f(xi),p)               
选取种子x0        2        ——        47
x1        5        ——        5
x2        26        1        26
x3        677        ——        19
x4        1631        1        33
x5        902        ——        9
x6        411        #NUM!        35
x7        1273        ——        4
x8        1850        1        17
x9        149        ——        8
x10        1005        1        18
x11        278        ——        43
x12        205        #NUM!        17
x13        1559        ——        8
x14        535        #NUM!        18
x15        1030        ——        43
x16        1051        #NUM!        17
x17        431        ——        8
x18        770        1        18
x19        1312        ——        43
x20        534        #NUM!        17
x21        1888        ——        8
x22        1522        1        18
x23        231        ——        43
x24        1333        47        17

yangchuanju

波拉德ρ法分解大整数                       
分解式        8131=173*47               
待分解数n        8131        ——        ——
生成多项式f(x)        x^2+1        gcd(x2k-xk,n)        gcd(f(xi),p)                       
选取种子x0        2        ——        173
x1        5        ——        5
x2        26        1        26
x3        677        ——        158
x4        2994        1        53
x5        3675        ——        42
x6        35        #NUM!        35
x7        1226        ——        15
x8        6973        173        53

yangchuanju

波拉德ρ法分解大整数                       
分解式        36287=131*277               
待分解数n        36287        ——        ——
生成多项式f(x)        x^2+1        gcd(x2k-xk,n)        gcd(f(xi),p)               
选取种子x0        2        ——        131
x1        5        ——        5
x2        26        1        26
x3        677        ——        22
x4        22886        1        92
x5        2439        ——        81
x6        33941        1        12
x7        24380        ——        14
x8        3341        #NUM!        66
x9        22173        ——        34
x10        25654        1        109
x11        26685        ——        92
x12        29425        #NUM!        81
x13        22806        ——        12
x14        12066        #NUM!        14
x15        4913        ——        66
x16        6715        1        34
x17        22772        ——        109
x18        22755        1        92
x19        10823        ——        81
x20        2894        #NUM!        12
x21        29227        ——        14
x22        21550        #NUM!        66
x23        1475        ——        34
x24        34693        1        109
x25        747        ——        92
x26        13705        #NUM!        81
x27        5514        ——        12
x28        31978        131        14

yangchuanju

波拉德p-1法分解大整数               
分解式        91=7*13       
待分解数n        91         gcd(ri-1, n)
取种子r0        2       
r1        2         1
r2        4         1
r3        64         7

附注：
r1=r0^1  (mod n)
r2=r1^2  (mod n)
r3=r2^3  (mod n)
r4=r3^4  (mod n)
……
下同，略

波拉德p-1法分解大整数               
分解式        143=13*11       
待分解数        143         最大公约数gcd
取种子r0        2       
r1        2         1
r2        4         1
r3        64         1
r4        27         13

波拉德p-1法分解大整数               
分解式        187=17*11       
待分解数        187         最大公约数gcd
取种子r0        2       
r1        2         1
r2        4         1
r3        64         1
r4        137         17

波拉德p-1法分解大整数               
分解式        253=11*23       
待分解数        253         最大公约数gcd
取种子r0        2       
r1        2         1
r2        4         1
r3        64         1
r4        27         1
r5        12         11

波拉德p-1法分解大整数               
分解式        299=13*23       
待分解数        299         最大公约数gcd
取种子r0        2       
r1        2         1
r2        4         1
r3        64         1
r4        27         13

yangchuanju

波拉德p-1法分解大整数               
分解式        5157437=2269*2273       
待分解数n        5157437         gcd(ri-1, n)
取种子r0        2       
r1        2         1
r2        4         1
r3        64         1
r4        1304905         1
r5        404913         1
r6        2157880         1
r7        4879227         1
r8        4379778         1
r9        4381440         2269

附注：
r1=r0^1  (mod n)
r2=r1^2  (mod n)
r3=r2^3  (mod n)
r4=r3^4  (mod n)
……
r9=r8^9  (mod n)