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

mathematica

137483460682971758231017855816043699329165454253307288357133379781794162674443
727360218481797830198550769882837374983036932333920470521165661950612603395593
都是78位素数

.·.·.

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

mathematica

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

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

.·.·.

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

分解用了8小时
我作弊了

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

mathematica

.·.·. 发表于 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 12:24
分解用了8小时
我作弊了

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

.·.·.

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

我是12线程CPU，Wall time只有8小时
参数是

1. python ./cado-nfs.py 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999929699 tasks.polyselect.import='/me/test.poly'

复制代码

而/me/test.poly文件的内容是

1. n: 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999929699
   
2. skew: 1.0
   
3. c5: 1
   
4. c0: -70301
   
5. Y1: -1
   
6. Y0: 10000000000000000000000000000000

复制代码

.·.·.

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还在分解吗

mathematica

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

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