数学研发论坛

 找回密码
 欢迎注册
查看: 330|回复: 8

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

[复制链接]
发表于 2020-8-8 19:27:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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,八个小时也算快了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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小时
参数是
  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
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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还在分解吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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。
(没有读文献,只 ...

我只理解了椭圆曲线的分解算法,这个特殊数域的筛法,暂时没理解为什么这么做
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-1-21 22:48 , Processed in 0.056118 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表