.·.·. 发表于 2019-1-25 09:47
2^2^14+1
应该是查的
毕竟是费马数的因子
2^2^14+2
也能分解。
2 · 3^2 · 1033 · 3049 · 112059721 · 1591582393<10> · 2932031007403<13> · 5831992772873<13> · 15686603697451<14> · 24474915268259<14> · 2028925864752043<16> · 38257184231365987<17> · 1588264559403825049<19> · 56713727820156410577229101238628035243<38> · 8272317928...13<56> · 1181109434...17<1568> · 2623595095...53<3145>
有一个是1568的整数，一个3145的整数
两个读是合数，你说怎么搞出来的呢？
mathematica 发表于 2019-1-25 09:09
2^2^14+1
这个也给出了结果，不过我认为是查询出来的
1169280858730743698290359938345963713403867034 ...
2^2^14+1 的查询结果与10^200+3的 结果有本质差别
对 10^200+3 给出的是3个素因子连乘， 符合楼主要求
对2^2^14+1 给出的是2个因子连乘， 不一定是素因子
2^(2^14)+1<4933> = 1169280858...13<54> · 1017489926...09<4880>
进一步查询得知 第一个因子 1169280858...13<54>是素数，
第二个因子1017489926...09<4880> 是合数，且不知其素因子
不符合楼主要求
factordb.com 很好，但本质是数据库查询系统，对于大数难题，常常查不到理想答案
本帖最后由 mathematica 于 2020-8-6 17:38 编辑
.·.·. 发表于 2019-1-25 01:09
第一个因子很容易找
00:25:54> factorint(10^200+3,1+4+8)
IFAC: cracking composite
ECM found a factor in curve #12, stage #2
Sigma=2363227094296319, B1=8000000, B2=800000000.
10^200+3 has a factor: 16892897616604738393032473779 (ECM curve 12, B1=8000000, B2=800000000)
我也用软件找到了这个因子，并且给出了sigma
[ <2, 2>, <3, 2>, <7, 1>, <3329, 1>, <4549, 1>, <15773, 1>, <690919, 1>, <406193003, 1> ]
因为这个光滑数，所以得到了这个因子，这个光滑数出卖了这个素数因子
mathematica 发表于 2020-8-6 17:37
ECM found a factor in curve #12, stage #2
Sigma=2363227094296319, B ...
ECM found a factor in curve #2, stage #2
Sigma=4920276195392524, B1=8000000, B2=800000000.
10^200+3 has a factor: 16892897616604738393032473779 (ECM curve 2, B1=8000000, B2=800000000)
估计两三分钟不到，找到了这个因子
FindGroupOrder := function (p, sigma)
K := GF(p);
v := K ! (4*sigma);
u := K ! (sigma^2-5);
x := u^3;
b := 4*x*v;
a := (v-u)^3*(3*u+v);
A := a/b-2;
x := x/v^3;
b := x^3 + A*x^2 + x;
E := EllipticCurve();
return FactoredOrder(E);
end function;
p:=16892897616604738393032473779;
sigma:=4920276195392524;
FindGroupOrder(p,sigma);
[ <2, 3>, <3, 2>, <5, 2>, <29, 1>, <186397, 1>, <196817, 1>, <449971, 1>, <19604131, 1> ]
http://magma.maths.usyd.edu.au/calc/
又是光滑数出卖了这个素数！
mathematica 发表于 2020-8-7 10:48
ECM found a factor in curve #2, stage #2
Sigma=4920276195392524, B1=8 ...
ECM found a factor in curve #7, stage #2
Sigma=2101670469519597, B1=8000000, B2=800000000.
10^200+3 has a factor: 16892897616604738393032473779 (ECM curve 7, B1=8000000, B2=800000000)
[ <2, 8>, <3, 1>, <17, 1>, <929, 1>, <2137, 1>, <243673, 1>, <295871, 1>, <9039907, 1> ]
mathematica 发表于 2020-8-7 11:00
ECM found a factor in curve #7, stage #2
Sigma=2101670469519597, B1=8 ...
ECM found a factor in curve #10, stage #2
Sigma=893918023258991, B1=8000000, B2=800000000.
10^200+3 has a factor: 16892897616604738393032473779 (ECM curve 10, B1=8000000, B2=800000000)
[ <2, 8>, <3, 2>, <31063, 1>, <211493, 1>, <1421309, 1>, <785224379, 1> ]
mathematica 发表于 2020-8-7 11:43
ECM found a factor in curve #10, stage #2
Sigma=893918023258991, B1=8 ...
08/11/20 09:01:17 v1.34.5 @ USER-20180508HK, prp29 = 16892897616604738393032473779 (curve 17 stg2 B1=10000008 sigma=3770300193 thread=0)
08/11/20 09:01:17 v1.34.5 @ USER-20180508HK, Finished 17 curves using Lenstra ECM method on C201 input, B1=10000008, B2=gmp-ecm default
感觉不错！这软件，大概花了十分钟左右，得到一个29位的素数因子，剩下的C172表示172位的合数
mathematica 发表于 2020-8-11 09:05
08/11/20 09:01:17 v1.34.5 @ USER-20180508HK, prp29 = 16892897616604738393032473779 (curve 17 stg2...
factorint(10^200+3)
IFAC: cracking composite
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
IFAC: checking for pure square
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 665-bit integer
Rho: using X^2-1 for up to 49152 rounds of 32 iterations
Rho: time = 932 ms, 24576 rounds
Rho: fast forward phase (8192 rounds of 64)...
Rho: time = 413 ms, 32772 rounds, back to normal mode
Rho: time = 244 ms, 40960 rounds
Rho: time = 266 ms, Pollard-Brent giving up.
IFAC: trying Shanks' SQUFOF, will fail silently if input
is too large for it.
IFAC: trying Lenstra-Montgomery ECM
ECM: working on 64 curves at a time; initializing for up to 220 rounds...
ECM: time = 0 ms
ECM: B1 = 1800, B2 = 198000, gss =128*420
ECM: time = 861 ms, B1 phase done, p = 1801, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 2017
ECM: time = 545 ms
ECM: B1 = 2200, B2 = 242000, gss =128*420
ECM: time = 985 ms, B1 phase done, p = 2203, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 2413
ECM: time = 632 ms
ECM: B1 = 2700, B2 = 297000, gss =256*420
ECM: time = 1249 ms, B1 phase done, p = 2707, setting up for B2
ECM: time = 17 ms, entering B2 phase, p = 2917
ECM: time = 772 ms
ECM: B1 = 3250, B2 = 357500, gss =256*420
ECM: time = 1422 ms, B1 phase done, p = 3251, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 3461
ECM: time = 904 ms
ECM: B1 = 4000, B2 = 440000, gss =256*420
ECM: time = 1664 ms, B1 phase done, p = 4001, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 4211
ECM: time = 1076 ms
ECM: B1 = 4850, B2 = 533500, gss =256*420
ECM: time = 2053 ms, B1 phase done, p = 4861, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 5077
ECM: time = 1303 ms
ECM: B1 = 5800, B2 = 638000, gss =256*420
ECM: time = 2475 ms, B1 phase done, p = 5801, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 6011
ECM: time = 1443 ms
ECM: B1 = 7100, B2 = 781000, gss =256*420
ECM: time = 2767 ms, B1 phase done, p = 7103, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 7313
ECM: time = 1792 ms
ECM: B1 = 8700, B2 = 957000, gss =256*420
ECM: time = 3907 ms, B1 phase done, p = 8707, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 8921
ECM: time = 2241 ms
ECM: B1 = 10600, B2 = 1166000, gss =512*420
ECM: time = 4368 ms, B1 phase done, p = 10601, setting up for B2
ECM: time = 20 ms, entering B2 phase, p = 10813
ECM: time = 2827 ms
ECM: B1 = 12900, B2 = 1419000, gss =512*420
ECM: time = 6017 ms, B1 phase done, p = 12907, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 13117
ECM: time = 3223 ms
ECM: B1 = 15700, B2 = 1727000, gss =512*420
ECM: time = 6468 ms, B1 phase done, p = 15727, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 15937
ECM: time = 3965 ms
ECM: B1 = 19000, B2 = 2090000, gss =512*420
ECM: time = 7982 ms, B1 phase done, p = 19001, setting up for B2
ECM: time = 17 ms, entering B2 phase, p = 19217
ECM: time = 4907 ms
ECM: B1 = 23200, B2 = 2552000, gss =512*420
ECM: time = 9698 ms, B1 phase done, p = 23201, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 23411
ECM: time = 5675 ms
ECM: B1 = 28000, B2 = 3080000, gss =512*420
ECM: time =11633 ms, B1 phase done, p = 28001, setting up for B2
ECM: time = 23 ms, entering B2 phase, p = 28223
ECM: time = 6416 ms
ECM: B1 = 34500, B2 = 3795000, gss =512*420
ECM: time =14322 ms, B1 phase done, p = 34501, setting up for B2
ECM: time = 16 ms, entering B2 phase, p = 34717
ECM: time = 7514 ms
ECM: B1 = 43000, B2 = 4730000, gss = 1024*420
ECM: time =17566 ms, B1 phase done, p = 43003, setting up for B2
ECM: time = 17 ms, entering B2 phase, p = 43219
ECM: time = 9777 ms
ECM: B1 = 53800, B2 = 5918000, gss = 1024*420
ECM: time =20504 ms, B1 phase done, p = 53813, setting up for B2
ECM: time = 16 ms, entering B2 phase, p = 54023
ECM: time =10757 ms
ECM: B1 = 67750, B2 = 7452500, gss = 1024*420
ECM: time =25413 ms, B1 phase done, p = 67751, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 67961
ECM: time =13933 ms
ECM: B1 = 85300, B2 = 9383000, gss = 1024*420
ECM: time =33857 ms, B1 phase done, p = 85303, setting up for B2
ECM: time = 19 ms, entering B2 phase, p = 85517
ECM: time =17912 ms
ECM: B1 = 107400, B2 = 11814000, gss = 1024*420
ECM: time =43500 ms, B1 phase done, p = 107441, setting up for B2
ECM: time = 16 ms, entering B2 phase, p = 107657
ECM: time =21778 ms
ECM: B1 = 135400, B2 = 14894000, gss = 1024*420
ECM: time =51415 ms, B1 phase done, p = 135403, setting up for B2
ECM: time = 26 ms, entering B2 phase, p = 135617
ECM: time =25173 ms
ECM: B1 = 170800, B2 = 18788000, gss = 1024*420
ECM: time =64824 ms, B1 phase done, p = 170801, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 171013
ECM: time =33090 ms
ECM: B1 = 215400, B2 = 23694000, gss = 1024*420
ECM: time =81681 ms, B1 phase done, p = 215417, setting up for B2
ECM: time = 16 ms, entering B2 phase, p = 215651
ECM: time =42665 ms
ECM: B1 = 271400, B2 = 29854000, gss = 1024*420
ECM: time = 105048 ms, B1 phase done, p = 271409, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 271637
ECM: time =53946 ms
ECM: B1 = 341500, B2 = 37565000, gss = 1024*420
ECM: time = 130142 ms, B1 phase done, p = 341501, setting up for B2
ECM: time = 18 ms, entering B2 phase, p = 341713
ECM: time =69894 ms
ECM: B1 = 429700, B2 = 47267000, gss = 1024*420
ECM: time = 169417 ms, B1 phase done, p = 429701, setting up for B2
ECM: time = 16 ms, entering B2 phase, p = 429923
ECM: time =26946 ms
found factor = 16892897616604738393032473779
IFAC: cofactor = 5919647550678682918318585392550030687321219331802429980672060525048639901448866420111089641083403610030206379807979210510870824800479444820240779860283084327969945191577457
IFAC: factor 5919647550678682918318585392550030687321219331802429980672060525048639901448866420111089641083403610030206379807979210510870824800479444820240779860283084327969945191577457
is composite
IFAC: factor 16892897616604738393032473779
is prime
IFAC: prime 16892897616604738393032473779
appears with exponent = 1
IFAC: main loop: 1 factor left
IFAC: cracking composite
5919647550678682918318585392550030687321219331802429980672060525048639901448866420111089641083403610030206379807979210510870824800479444820240779860283084327969945191577457
IFAC: checking for pure square
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 571-bit integer
Rho: using X^2+5 for up to 49152 rounds of 32 iterations
Rho: time = 822 ms, 24576 rounds
Rho: fast forward phase (8192 rounds of 64)...
Rho: time = 394 ms, 32772 rounds, back to normal mode
Rho: time = 235 ms, 40960 rounds
Rho: time = 229 ms, Pollard-Brent giving up.
IFAC: trying Shanks' SQUFOF, will fail silently if input
is too large for it.
IFAC: trying Lenstra-Montgomery ECM
ECM: working on 64 curves at a time; initializing for up to 173 rounds...
ECM: time = 0 ms
ECM: B1 = 1800, B2 = 198000, gss =128*420
ECM: time = 692 ms, B1 phase done, p = 1801, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 2017
ECM: time = 471 ms
ECM: B1 = 2200, B2 = 242000, gss =128*420
ECM: time = 840 ms, B1 phase done, p = 2203, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 2413
ECM: time = 507 ms
ECM: B1 = 2700, B2 = 297000, gss =256*420
ECM: time = 1003 ms, B1 phase done, p = 2707, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 2917
ECM: time = 604 ms
ECM: B1 = 3250, B2 = 357500, gss =256*420
ECM: time = 1107 ms, B1 phase done, p = 3251, setting up for B2
ECM: time = 13 ms, entering B2 phase, p = 3461
ECM: time = 741 ms
ECM: B1 = 4000, B2 = 440000, gss =256*420
ECM: time = 1453 ms, B1 phase done, p = 4001, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 4211
ECM: time = 879 ms
ECM: B1 = 4850, B2 = 533500, gss =256*420
ECM: time = 1612 ms, B1 phase done, p = 4861, setting up for B2
ECM: time = 11 ms, entering B2 phase, p = 5077
ECM: time = 1031 ms
ECM: B1 = 5800, B2 = 638000, gss =256*420
ECM: time = 2051 ms, B1 phase done, p = 5801, setting up for B2
ECM: time = 13 ms, entering B2 phase, p = 6011
ECM: time = 1172 ms
ECM: B1 = 7100, B2 = 781000, gss =256*420
ECM: time = 2447 ms, B1 phase done, p = 7103, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 7313
ECM: time = 1676 ms
ECM: B1 = 8700, B2 = 957000, gss =256*420
ECM: time = 2978 ms, B1 phase done, p = 8707, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 8921
ECM: time = 1830 ms
ECM: B1 = 10600, B2 = 1166000, gss =512*420
ECM: time = 3611 ms, B1 phase done, p = 10601, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 10813
ECM: time = 2122 ms
ECM: B1 = 12900, B2 = 1419000, gss =512*420
ECM: time = 4171 ms, B1 phase done, p = 12907, setting up for B2
ECM: time = 12 ms, entering B2 phase, p = 13117
ECM: time = 2564 ms
ECM: B1 = 15700, B2 = 1727000, gss =512*420
ECM: time = 5355 ms, B1 phase done, p = 15727, setting up for B2
ECM: time = 11 ms, entering B2 phase, p = 15937
ECM: time = 3090 ms
ECM: B1 = 19000, B2 = 2090000, gss =512*420
ECM: time = 6011 ms, B1 phase done, p = 19001, setting up for B2
ECM: time = 13 ms, entering B2 phase, p = 19217
ECM: time = 3367 ms
ECM: B1 = 23200, B2 = 2552000, gss =512*420
ECM: time = 7231 ms, B1 phase done, p = 23201, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 23411
ECM: time = 4046 ms
ECM: B1 = 28000, B2 = 3080000, gss =512*420
ECM: time = 9137 ms, B1 phase done, p = 28001, setting up for B2
ECM: time = 11 ms, entering B2 phase, p = 28223
ECM: time = 4853 ms
ECM: B1 = 34500, B2 = 3795000, gss =512*420
ECM: time =10440 ms, B1 phase done, p = 34501, setting up for B2
ECM: time = 19 ms, entering B2 phase, p = 34717
ECM: time = 5798 ms
ECM: B1 = 43000, B2 = 4730000, gss = 1024*420
ECM: time =12679 ms, B1 phase done, p = 43003, setting up for B2
ECM: time = 12 ms, entering B2 phase, p = 43219
ECM: time = 6920 ms
ECM: B1 = 53800, B2 = 5918000, gss = 1024*420
ECM: time =15952 ms, B1 phase done, p = 53813, setting up for B2
ECM: time = 16 ms, entering B2 phase, p = 54023
ECM: time = 8713 ms
ECM: B1 = 67750, B2 = 7452500, gss = 1024*420
ECM: time =20493 ms, B1 phase done, p = 67751, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 67961
ECM: time =11596 ms
ECM: B1 = 85300, B2 = 9383000, gss = 1024*420
ECM: time =26326 ms, B1 phase done, p = 85303, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 85517
ECM: time =14705 ms
ECM: B1 = 107400, B2 = 11814000, gss = 1024*420
ECM: time =33397 ms, B1 phase done, p = 107441, setting up for B2
ECM: time = 17 ms, entering B2 phase, p = 107657
ECM: time =15557 ms
ECM: B1 = 135400, B2 = 14894000, gss = 1024*420
ECM: time =40620 ms, B1 phase done, p = 135403, setting up for B2
ECM: time = 13 ms, entering B2 phase, p = 135617
ECM: time =21753 ms
ECM: B1 = 170800, B2 = 18788000, gss = 1024*420
ECM: time =54020 ms, B1 phase done, p = 170801, setting up for B2
ECM: time = 14 ms, entering B2 phase, p = 171013
ECM: time =26966 ms
ECM: B1 = 215400, B2 = 23694000, gss = 1024*420
ECM: time =65318 ms, B1 phase done, p = 215417, setting up for B2
ECM: time = 12 ms, entering B2 phase, p = 215651
ECM: time =32216 ms
ECM: B1 = 271400, B2 = 29854000, gss = 1024*420
ECM: time =84390 ms, B1 phase done, p = 271409, setting up for B2
ECM: time = 15 ms, entering B2 phase, p = 271637
ECM: time =41819 ms
ECM: B1 = 341500, B2 = 37565000, gss = 1024*420
ECM: time = 104850 ms, B1 phase done, p = 341501, setting up for B2
ECM: time = 17 ms, entering B2 phase, p = 341713
ECM: time =50177 ms
ECM: B1 = 429700, B2 = 47267000, gss = 1024*420
ECM: time = 126526 ms, B1 phase done, p = 429701, setting up for B2
ECM: time = 12 ms, entering B2 phase, p = 429923
ECM: time =63064 ms
ECM: B1 = 540400, B2 = 59444000, gss = 1024*420
^C*** at top-level: factorint(10^200+3)
*** ^-------------------
*** factorint: user interrupt after 36min, 57,769 ms
*** Break loop: <Return> to continue; 'break' to go back to GP prompt
pari/GP也找到了相同的结果
找到这个因子并不麻烦
（只是我不知道该怎么要求Pari/GP找到这个因子之后停止，于是浪费了太多时间）
Pari/GP分解因数的效率其实挺高的
.·.·. 发表于 2020-8-18 15:31
pari/GP也找到了相同的结果
找到这个因子并不麻烦
（只是我不知道该怎么要求Pari/GP找到这个因子之后 ...
你的pari/gp为什么会输出那么多东西呀，我的不会输出那么多东西
mathematica 发表于 2020-8-21 13:52
你的pari/gp为什么会输出那么多东西呀，我的不会输出那么多东西
\g 4
factorint(...)
大概效果是这样的
neutron@Neutron:/me$ gp
Reading GPRC: /etc/gprc ...Done.
GP/PARI CALCULATOR Version 2.11.4 (released)
amd64 running linux (x86-64/GMP-6.2.0 kernel) 64-bit version
compiled: Apr 25 2020, gcc version 9.3.0 (Arch Linux 9.3.0-1)
threading engine: pthread
(readline v8.0 enabled, extended help enabled)
Copyright (C) 2000-2018 The PARI Group
PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit.
Type ?17 for how to get moral (and possibly technical) support.
parisizemax = 34359738368, primelimit = 67108864, nbthreads = 12
18:44:22> \g 4
debug = 4
18:44:24> factorint(2^67-1)
IFAC: cracking composite
147573952589676412927
IFAC: checking for pure square
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 67-bit integer
Rho: using X^2+5 for up to 57 rounds of 32 iterations
Rho: time = 1 ms, Pollard-Brent giving up.
IFAC: trying Shanks' SQUFOF, will fail silently if input
is too large for it.
IFAC: trying Lenstra-Montgomery ECM
ECM: number too small to justify this stage
IFAC: trying MPQS
MPQS: number to factor N = 147573952589676412927
MPQS: factoring number of 21 decimal digits
MPQS: sieving interval = [-4500, 4500]
MPQS: size of factor base = 121
MPQS: striving for 163 relations
MPQS: coefficients A will be built from 3 primes each
MPQS: primes for A to be chosen near FB = 179
MPQS: smallest prime used for sieving FB = 5
MPQS: largest prime in FB = 1697
MPQS: bound for `large primes' = 1697
MPQS: first sorting at 40%, then every 10.0% / 5.0%
MPQS: passing the 40.0% sort point, time = 1 ms
MPQS: done sorting, time = 0 ms
MPQS: found 41.1% of the required relations
MPQS: passing the 51.1% sort point, time = 0 ms
MPQS: done sorting, time = 0 ms
MPQS: found 51.5% of the required relations
MPQS: passing the 61.5% sort point, time = 0 ms
MPQS: done sorting, time = 0 ms
MPQS: found 60.7% of the required relations
MPQS: passing the 70.7% sort point, time = 0 ms
MPQS: done sorting, time = 0 ms
MPQS: found 72.3% of the required relations
MPQS: passing the 82.3% sort point, time = 0 ms
MPQS: done sorting, time = 0 ms
MPQS: found 82.2% of the required relations
MPQS: passing the 87.2% sort point, time = 0 ms
MPQS: done sorting, time = 0 ms
MPQS: found 89.5% of the required relations
MPQS: passing the 94.5% sort point, time = 0 ms
MPQS: done sorting, time = 0 ms
MPQS: found 100.0% of the required relations
MPQS: starting Gauss over F_2 on 163 relations
MPQS: Gauss done: kernel has rank 48, taking gcds...
MPQS: time in Gauss and gcds = 0 ms
MPQS: found factors = 761838257287
and 193707721
IFAC: factor 761838257287
is prime
IFAC: factor 193707721
is prime
IFAC: prime 193707721
appears with exponent = 1
IFAC: main loop: 1 factor left
IFAC: prime 761838257287
appears with exponent = 1
IFAC: main loop: this was the last factor
IFAC: found 2 large prime (power) factors.
time = 3 ms.
%1 =
[ 193707721 1]
18:44:26>