论坛 › 数学欣赏 › 10^155-70301大整数分解欣赏

mathematica 发表于 2020-8-8 19:27:04

10^155-70301大整数分解欣赏

137483460682971758231017855816043699329165454253307288357133379781794162674443
727360218481797830198550769882837374983036932333920470521165661950612603395593
都是78位素数

.·.·. 发表于 2020-8-11 17:47:16

yafu分解这个需要多久？
Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire factorization: 292848/32582.9
727360218481797830198550769882837374983036932333920470521165661950612603395593 137483460682971758231017855816043699329165454253307288357133379781794162674443

mathematica 发表于 2020-8-12 08:40:15

.·.·. 发表于 2020-8-11 17:47
yafu分解这个需要多久？
Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for ...

应该会很久很就，你分解了多长时间？
我是从网上摘抄过来的，不是我分解的

.·.·. 发表于 2020-8-12 12:24:45

mathematica 发表于 2020-8-12 08:40
应该会很久很就，你分解了多长时间？
我是从网上摘抄过来的，不是我分解的

分解用了8小时
我作弊了

用的是SNFS而不是默认的选项
一般的合数用不了SNFS

mathematica 发表于 2020-8-12 14:01:21

.·.·. 发表于 2020-8-12 12:24
分解用了8小时
我作弊了



Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire factorization: 292848/32582.9

这个292848，292848/3600=81.3466666667，不是81个小时吗？
我到目前都不会用snfs，八个小时也算快了

mathematica 发表于 2020-8-12 14:07:38

.·.·. 发表于 2020-8-12 12:24
分解用了8小时
我作弊了



我到现在都不会特殊数域算法，
你的参数之类的怎么弄的？
把你的命令行，以及读取的参数文件，弄上来看看

.·.·. 发表于 2020-8-12 17:49:31

mathematica 发表于 2020-8-12 14:07
我到现在都不会特殊数域算法，
你的参数之类的怎么弄的？
把你的命令行，以及读取的参数文件，弄上来看 ...

我是12线程CPU，Wall time只有8小时
参数是python ./cado-nfs.py 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999929699 tasks.polyselect.import='/me/test.poly'而/me/test.poly文件的内容是n: 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999929699
skew: 1.0
c5: 1
c0: -70301
Y1: -1
Y0: 10000000000000000000000000000000

.·.·. 发表于 2020-8-13 18:46:38

mathematica 发表于 2020-8-12 14:07
我到现在都不会特殊数域算法，
你的参数之类的怎么弄的？
把你的命令行，以及读取的参数文件，弄上来看 ...

SNFS最主要的是找到多项式f(x)和有理数p/q，使得f(p/q)=0(mod n)
然后令g(x)=p-qx。
（没有读文献，只是这样恰好管用）
比如10^155-70301，可以取f(x)=x^5-70301而f(10^31/1)=0
从而取g(x)=10^31-x即可

当然如果你取f(x)=10000*x^5-70301而g(x)取10^30-x也可以，没人拦着你这么做

这里取什么多项式并不影响最终结果，只影响第一步筛法生成relation的速度。4

话说你的yafu还在分解吗;P

mathematica 发表于 2020-8-14 08:02:35

.·.·. 发表于 2020-8-13 18:46
SNFS最主要的是找到多项式f(x)和有理数p/q，使得f(p/q)=0(mod n)
然后令g(x)=p-qx。
（没有读文献，只 ...

我只理解了椭圆曲线的分解算法，这个特殊数域的筛法，暂时没理解为什么这么做

查看完整版本: 10^155-70301大整数分解欣赏