整数分解方法探讨

yangchuanju · 发表于 2025-12-9 19:51

本帖最后由 yangchuanju 于 2025-12-9 20:49 编辑

波拉德p-1法分解大整数
分解式 7331117=641*11437
待分解数n 7331117 gcd(ri-1, n)
取种子r0 2
r1 2 1
r2 4 1
r3 64 1
r4 2114982 1
r5 2937380 1
r6 6647270 1
r7 2561195 1
r8 3875332 1
r9 3838154 1
r10 6535635 1
r11 2937061 1
r12 3141542 641

附注：
r1=r0^1  (mod n)
r2=r1^2  (mod n)
r3=r2^3  (mod n)
r4=r3^4  (mod n)
……
r12=r11^12  (mod n)

yangchuanju · 发表于 2025-12-9 21:12

本帖最后由 yangchuanju 于 2025-12-9 21:40 编辑

用连分数法分解大整数1
迭代式中，P0=0，Q0=1随机取定，αk=(Pk+n^0.5)/Qk，ak=[αk]，Pk+1=ak*Qk-Pk，Qk+1=(n-(pk+1)^2)/Qk，k=0,1,2,3……，k和k+1是各参数的下标。
待分解数n 1037
k P Q α=(P+n^0.5)/Q a=int(α)
0 0 1 32.20248438 32
1 32 13 4.938652644 4
2 20 49 1.065356824 1

既已找到了一个Q2=49=7^2，（Q必须是是平方数且下标是偶数，下同，略）可解同余方程p^2==7^2 (mod 1037)，
得p=129，129^2-7^2==0 (mod 1037)
GCD(129+7,1037)= 17
GCD(129-7,1037)= 61
最后得分解式1037=17*61

yangchuanju · 发表于 2025-12-9 21:16

本帖最后由 yangchuanju 于 2025-12-9 21:18 编辑

用连分数法分解大整数2
迭代式中，P0=0，Q0=1随机取定，αk=(Pk+n^0.5)/Qk，ak=[αk]，Pk+1=ak*Qk-Pk，Qk+1=(n-(pk+1)^2)/Qk，k=0,1,2,3……，k和k+1是各参数的下标。
待分解数n 1000009
k P Q α=(P+n^0.5)/Q a=int(α)
0 0 1 1000.0045 1000
1 1000 9 222.2227222 222
2 998 445 4.489897753 4
3 782 873 2.041242268 2
4 964 81 24.24696914 24
5 980 489 4.049088957 4
6 976 97 20.37118041 20
7 964 729 2.694107682 2
8 494 1037 1.44069865 1
9 543 680 2.269124265 2
10 817 489 3.715755624 3
11 650 1181 1.397124894 1
12 531 608 2.518099507 2
13 685 873 1.930131157 1
14 188 1105 1.075117195 1
15 917 144 13.31253125 13
16 955 611 3.199680033 3
17 878 375 5.008012 5
18 997 16 124.8127812 124
19 987 1615 1.230343344 1
20 628 375 4.341345333 4

虽已找到了一个Q4=81=9^2，但同余方程p^2==9^2 (mod 1000009)无整数解，
继续向下找，又找到一个Q18=16=4^2，解同余方程p^2==4^2 (mod 1000009)，
得p=494881，494881^2-4^2==0 (mod 1000009)
GCD(494881+4,1000009)= 3413
GCD(494881-4,1000009)= 293
最后得分解式1000009=293*3413

yangchuanju · 发表于 2025-12-9 21:21

本帖最后由 yangchuanju 于 2025-12-9 21:24 编辑

用连分数法分解大整数3
迭代式中，P0=0，Q0=1随机取定，αk=(Pk+n^0.5)/Qk，ak=[αk]，Pk+1=ak*Qk-Pk，Qk+1=(n-(pk+1)^2)/Qk，k=0,1,2,3……，k和k+1是各参数的下标。
待分解数n 119
k P Q α=(P+n^0.5)/Q a=int(α)
0 0 1 10.90871211 10
1 10 19 1.100458532 1
2 9 2 9.954356057 9
3 9 19 1.047826953 1
4 10 1 20.90871211 20

既已找到了一个Q4=1=1^2，可解同余方程p^2==1^2 (mod 119)，
得p=50，50^2-1^2==0 (mod 119)
GCD(50+1,119)= 17
GCD(50-1,119)= 7
最后得分解式119=7*17

yangchuanju · 发表于 2025-12-9 21:23

用连分数法分解大整数4
迭代式中，P0=0，Q0=1随机取定，αk=(Pk+n^0.5)/Qk，ak=[αk]，Pk+1=ak*Qk-Pk，Qk+1=(n-(pk+1)^2)/Qk，k=0,1,2,3……，k和k+1是各参数的下标。
待分解数n 1537
k P Q α=(P+n^0.5)/Q a=int(α)
0 0 1 39.20459157 39
1 39 16 4.887786973 4
2 25 57 1.126396343 1
3 32 9 7.911621285 7
4 31 64 1.096946743 1

既已找到了一个Q4=64=8^2，可解同余方程p^2==8^2 (mod 1537)，
得p=485，485^2-8^2==0 (mod 1537)
GCD(485+8,1537)= 29
GCD(485-8,1537)= 53
最后得分解式1537=29*53

yangchuanju · 发表于 2025-12-9 21:36

本帖最后由 yangchuanju 于 2025-12-9 21:38 编辑

用连分数法分解大整数5
迭代式中，P0=0，Q0=1随机取定，αk=(Pk+n^0.5)/Qk，ak=[αk]，Pk+1=ak*Qk-Pk，Qk+1=(n-(pk+1)^2)/Qk，k=0,1,2,3……，k和k+1是各参数的下标。
待分解数n 13290059
k P Q α=(P+n^0.5)/Q a=int(α)
0 0 1 3645.553319 3645
1 3645 4034 1.80727648 1
2 389 3257 1.238732981 1
3 2868 1555 4.188780269 4
4 3352 1321 5.297163754 5
5 3253 2050 3.36514796 3
6 2897 2389 2.738615872 2
7 1881 4082 1.353883714 1
8 2201 2069 2.825787008 2
9 1937 4610 1.210966013 1
10 2673 1333 4.740100014 4
……
52 3628 25 290.9421328 290
……
88 2692 1681 3.770109053 3
……
102 3553 625 11.51768531 11
……
222 2947 4225 1.560367649 1
……

迭代表中，虽有多组偶下标且是平方数的参数Q，但只要第3组Q102=625=25^2是有效的，
既已找到了一个Q102=625=25^2（第3个平方偶下标Q），可解同余方程p^2==25^2 (mod 13290059)，
得（625+13290059*68544=954439^2）p=954439，954439^2-25^2==0 (mod 13290059)
GCD(954439+25,13290059)= 4261
GCD(954439-25,13290059)= 3119
最后得分解式13290059=3119*4261

白新岭 · 发表于 2025-12-9 22:33

涉猎广泛，有足够的时间投入研究。
而对于我来说，只是忙里偷闲，在完成本职工作后，有空闲时上上网。
如果，白天有空时，也许编个程序运算，获得数据，好验证自己的推论。

		自动登录	找回密码
密码			注册