找回密码
 欢迎注册
查看: 3235|回复: 18

[分享] 最小的还没被分解的梅森合数M1277

[复制链接]
发表于 2023-4-12 14:46:30 | 显示全部楼层 |阅读模式

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

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

×
本帖最后由 nyy 于 2023-4-12 15:05 编辑
  1. PrimeQ[2^1277 - 1]
复制代码


这个数,肯定是一个合数。

但是只知道是合数,没有给出任何因子!

About M1277
https://www.mersenneforum.org/showthread.php?t=27835


"I came here for an argument" about...] Base 10 digits of M1277 and its length
https://www.mersenneforum.org/showthread.php?p=625284


PrimeNet Exponent Status
https://www.mersenne.org/report_exponent/?exp_lo=1277&full=1


Behold, "The World's Most Secure RSA key" : 2^1277-1
https://www.mersenneforum.org/showthread.php?p=525906#post525906



I want to factorize 2^1277-1
https://www.mersenneforum.org/sh ... &highlight=1277



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-12 17:58:25 | 显示全部楼层
本帖最后由 灵树 于 2023-4-12 18:02 编辑

\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-12 19:41:30 | 显示全部楼层
灵树 发表于 2023-4-12 17:58
\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918 ...

385位整数,估计过不了多少年就分解了!
估计是两个素数或者三个素数的乘积,
四个素数的乘积可能性不大!
五个估计就是胡扯!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-13 08:46:46 | 显示全部楼层
梅森数M1061分解报告
https://bbs.emath.ac.cn/forum.ph ... 1&fromuid=14149


2^1061-1=P143*P177
这是一个320位的大合数
被分解成了两个素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-13 13:59:17 | 显示全部楼层
灵树 发表于 2023-4-12 17:58
\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918 ...
  1. Clear["Global`*"];(*清除所有变量*)
  2. n=2^1277-1
  3. r=PowerMod[3,(n-1),n](*如果n是素数,那么3^(n-1)=1(mod n)*)
  4. If[r!=1,Print["根据费马小定理,这个整数不是素数!"]]
复制代码


这个整数是
2601983048666099770481310081841021384653815561816676201329778087600902\
0149183400745030598604330810462106054034885702519478458915620808662270\
3497665141933019073103237734730508644329583741539588761823985513692245\
2802923419286887119716740625346109565072933087221327790207134604146257\
0639011665562079727297004617670555507851302566746088721832395072195127\
17434046725178680177638925792182271

3^(n-1) mod n等于
1996918483046192319418122671585765807718685366219813077922752650677677\
9512676029862611571000323448537136431958018953815203841620633009240830\
7743662806783988118840125641694946643656661146859555511032219018822768\
4871208684545734968898994412714940405294059254336336551040601253189846\
8569119087415292543381643175741203010905029856987474463873997016126136\
05350163144326174904132157662013184

根据费马小定理,n一定是合数!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-16 10:53:45 | 显示全部楼层
有没有一种算法可以估算出分解一个这样的数需要多长时间,比如:\[y=ax^3\],y是总计算时间,a是硬件速度,x是数据位数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-17 11:28:11 | 显示全部楼层
灵树 发表于 2023-4-16 10:53
有没有一种算法可以估算出分解一个这样的数需要多长时间,比如:\[y=ax^3\],y是总计算时间,a是硬件速度,x ...

https://www.mersenne.org/report_exponent/?exp_lo=1277&full=1

这个是对找小因子的尝试,结果都失败了!

点评

no factor from 2^1 to 2^68  发表于 2023-4-17 12:06
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-17 14:22:05 | 显示全部楼层
灵树 发表于 2023-4-16 10:53
有没有一种算法可以估算出分解一个这样的数需要多长时间,比如:\[y=ax^3\],y是总计算时间,a是硬件速度,x ...

Page 15 of https://eprint.iacr.org/2014/653.pdf summarizes matrix size and CPU-time for a list of mersenne factorizations completed by the CADO group.

Sampling, 2^1123-1 was 124M matrix, and took 55 core-years.
2^1199-1 (the largest solved yet) was 270M matrix, and took 190 core-years.
Those are 76 bits apart; M1277 is 78 bits larger, so let's scale:
270/124 = 2.18, so M1277 might be 2.18 * 270M = ~520M matrix.
190/55 = 3.45, so M1277's matrix might take 3.45 * 190 = ~660 core-years.

I don't think any single machine is going to handle that, even if memory weren't a constraint. MPI splits the matrix in a way that also splits the memory requirement, so even if this matrix requires 200GB a cluster of 16 machines could solve it with normal amounts of memory.

A similar scaling of Greg's M1061 note of 3 CPU-centuries sieve time is sobering.
Edit to add: Table 2 page 11 of the above linked paper lists sieve data. For 2^1199-1: 37-bit large primes, mfbr = 109, mfba = 74, 13G raw relations. Not sure whether M1277 would best use 38 or 39 bit LP; let's say 39 and aim for 40G relations.

https://www.mersenneforum.org/sh ... 10&postcount=10

这儿说了,光是矩阵,大概就520百万行(文中没说,也可能是列)。



Filtering was performed using the MSIEVE software library [10]. Filtering started with
the set of approximately 671 million unique relations. Following the singleton and clique
removal steps, the matrix had approximate 282 million rows

这是M1061的数据,用了282百万行。
https://eprint.iacr.org/2012/444.pdf
https://bbs.emath.ac.cn/forum.ph ... &highlight=1061
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-17 14:46:34 | 显示全部楼层
Factorization of a 768-bit RSA modulus

https://hal.inria.fr/file/index/docid/444693/filename/rsa768.pdf

突然发现bing搜索结果也不错,搜索英文比烂百度烂搜狗强多了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-4-18 09:13:43 | 显示全部楼层
本帖最后由 nyy 于 2023-4-18 09:16 编辑

分享一个大整数的分解2^727-1
https://bbs.emath.ac.cn/forum.ph ... 3&fromuid=14149
P98*P122=C219=M727


分享一个594位的大整数完全分解
10^593+1=11*P73*P520
https://bbs.emath.ac.cn/forum.ph ... 4&fromuid=14149
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-5-27 16:46 , Processed in 0.067670 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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