找回密码
 欢迎注册
查看: 23741|回复: 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-29 08:41:51 | 显示全部楼层
wsc810 发表于 2020-10-28 20:59
你用的什么软件

有时间去考证书,比如注册会计师等,
不要研究素数判定、整数分解,虽然我觉得这两个问题真的非常有趣!
但是真的是太难太难了!白白浪费你的时间!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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-30 10:55:33 | 显示全部楼层
mathematica 发表于 2020-10-30 08:35
2224442340713
这个数,你用2 3 5 7为基分解给我看一下呗

去掉2,3,5,7用ECM呢?
“基”之所以是“基”,意思很简单,它们是可替代的。
ECM算一个数,如果假设这个数的order不被2,3,5,7整除,会死得很惨。

如果真的2,3,5,7分解2224442340713,NFS会非常慢,这里可以直接用QFS
(虽然QFS也快不到哪里去)

my(c=(2*3*5*7)^500);parfor(i=1,10000000,my(x=(sqrtint(2224442340713*i)+1)^2%2224442340713);if(gcd(x,c)==x,print(i)))
(懒得写检测一个数字是2,3,5,7的乘积的算法了,直接gcd搞定)
得到
174953
699812
1574577
2164253
2331353
2455773
2799248
4373825
6298308
7529723
7864001
8572697
8657012
9325412
9823092
time = 29,776 ms.

把这些输出统一处理一下
z=[174953,699812,1574577,2164253,2331353,2455773,2799248,4373825,6298308,7529723,7864001,8572697,8657012,9325412,9823092]
apply(x->print(x),apply(x->factor((sqrtint(2224442340713*x)+1)^2%2224442340713),z))
输出
[2, 8; 3, 7; 5, 1]
[2, 10; 3, 7; 5, 1]
[2, 8; 3, 9; 5, 1]
...
比较走运的,x[10]直接符合题意(x[10]^2和x[10]^2%2224442340713都是完全平方数且后者恰好是2,3,5,7为基筛出来的东西)
gcd(x[10]+3*5^5*7,2224442340713)
可以直接得到答案

现在该你了
随便选ECM,一切初始值随意,分解2224442340713,要求是分解时候使用的order不是2,3,5,7的倍数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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-3-28 16:37 , Processed in 0.084695 second(s), 22 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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