找回密码
 欢迎注册
查看: 42302|回复: 32

[求助] 一个564位大整数分解

[复制链接]
发表于 2020-10-25 07:56:28 | 显示全部楼层 |阅读模式

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

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

×
本帖最后由 wsc810 于 2020-10-25 08:10 编辑

  n=1734624471791475554302589708643097783774218447236640846493470190613635\
7919287910885759103833040883717798381086845154642194071297830613418986\
4280826014542758708589243873685563973118948869399158545506611147420216\
1325570172605641393943669457932209686651089596854827053880726458285541\
5193640191246493118254609287981573305779557335850498227928009094287256\
7591518912118622751714319229788100979251036035496917279912663527358783\
2366471931547770914277453770382945849189175903251109393813224860442985\
7397165071105924446217754254070691304703466464360349138244172330659883\
4176

这个数是费马数$F_11$的一个564位素因子减一得到的数值


F11=319489 × 974849 × 167988556341760475137 × 3560841906445833920513 × P564




这个数目前能完全分解么,找到它的小素因子也可以
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-25 08:17:22 | 显示全部楼层
本帖最后由 mathematica 于 2020-10-25 08:23 编辑
  1. n=173462447179147555430258970864309778377421844723664084649347019061363579192879108857591038330408837177983810868451546421940712978306134189864280826014542758708589243873685563973118948869399158545506611147420216132557017260564139394366945793220968665108959685482705388072645828554151936401912464931182546092879815733057795573358504982279280090942872567591518912118622751714319229788100979251036035496917279912663527358783236647193154777091427745377038294584918917590325110939381322486044298573971650711059244462177542540706913047034664643603491382441723306598834176
  2. m=2^13*139*1847*32488628503*1847272285831883*92147345984208191
  3. aaa=n/m
复制代码


n=173462447179147555430258970864309778377421844723664084649347019061363579192879108857591038330408837177983810868451546421940712978306134189864280826014542758708589243873685563973118948869399158545506611147420216132557017260564139394366945793220968665108959685482705388072645828554151936401912464931182546092879815733057795573358504982279280090942872567591518912118622751714319229788100979251036035496917279912663527358783236647193154777091427745377038294584918917590325110939381322486044298573971650711059244462177542540706913047034664643603491382441723306598834176
m=2^13*139*1847*32488628503*1847272285831883*92147345984208191
aaa=n/m



1847272285831883
92147345984208191
32488628503
139
1847
2^13
这些都是因子
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-25 08:28:16 | 显示全部楼层
mathematica 发表于 2020-10-25 08:17
n=1734624471791475554302589708643097783774218447236640846493470190613635791928791088575910383304 ...

23位的因子23918760924164258488261
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-26 14:52:27 | 显示全部楼层
大整数分解很难,而且根据我的人生经验,似乎所有的有效分解算法,都依赖于小素数!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-26 23:12:43 | 显示全部楼层
mathematica 发表于 2020-10-26 14:52
大整数分解很难,而且根据我的人生经验,似乎所有的有效分解算法,都依赖于小素数!

GNFS不是
但问题在于
GNFS也分解不了
现在剩下的这1624 bit,大概snfs应该也分解不出
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-27 08:21:24 | 显示全部楼层
.·.·. 发表于 2020-10-26 23:12
GNFS不是
但问题在于
GNFS也分解不了

http://www.docin.com/p-436516064.html

我感觉你又胡说八道了!
QQ截图20201027082039.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-27 19:57:00 | 显示全部楼层
mathematica 发表于 2020-10-27 08:21
http://www.docin.com/p-436516064.html

我感觉你又胡说八道了!

NFS跟你想的不一样
NFS对基底的要求并不高
并不是要求一个数字一定有一个非常好看的约数。

NFS的本质就是找到类似x^2=y^2(mod n)但是x不等于正负y的一组解(只是类似,具体我没仔细研究)
论文里面说的是,我们要借助RFB寻找一个类似x^2=y^2(mod n)的结果
到这一步为止,我们对原数n没有任何假设。不管n的因子长什么样子,我们都可以用这种算法。

所以n的分解不会依赖某些$特定的$小素数。

当然你说”依赖于小素数“的意思是,只要素数出现过一次就算出现过,那你当我是胡说就好了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 10:45:58 | 显示全部楼层
.·.·. 发表于 2020-10-27 19:57
NFS跟你想的不一样
NFS对基底的要求并不高
并不是要求一个数字一定有一个非常好看的约数。

都需要小素数试除,把这个搞成光滑数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 10:48:47 | 显示全部楼层
.·.·. 发表于 2020-10-27 19:57
NFS跟你想的不一样
NFS对基底的要求并不高
并不是要求一个数字一定有一个非常好看的约数。

也许只有量子分解算法不依赖小素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 12:59:24 | 显示全部楼层
mathematica 发表于 2020-10-28 10:45
都需要小素数试除,把这个搞成光滑数

并不是
NFS分解只需要拿小素数做一组基
我简单地用MPQS来解释一下好了(虽然可能不对但原理类似)
在mod n意义下
比如你得到a^2=p1p2,b^2=p2p3,c^2=p1p3,那么(abc)^2=(p1p2p3)^2
如果abc不等于正负p1p2p3,那么我们就可以直接得到abc+p1p2p3和abc-p1p2p3都与n有非平凡的公约数

在这一过程中p1p2p3只起到了基底的作用
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-12-7 08:11 , Processed in 0.027645 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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