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

nyy

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

灵树

\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271

nyy

灵树 发表于 2023-4-12 17:58
\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918 ...

385位整数，估计过不了多少年就分解了！
估计是两个素数或者三个素数的乘积，
四个素数的乘积可能性不大！
五个估计就是胡扯！

nyy

梅森数M1061分解报告
https://bbs.emath.ac.cn/forum.ph ... 1&fromuid=14149


2^1061-1=P143*P177
这是一个320位的大合数
被分解成了两个素数

nyy

灵树 发表于 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一定是合数！

灵树

有没有一种算法可以估算出分解一个这样的数需要多长时间，比如：\[y=ax^3\],y是总计算时间，a是硬件速度，x是数据位数。

nyy

灵树 发表于 2023-4-16 10:53
有没有一种算法可以估算出分解一个这样的数需要多长时间，比如：\[y=ax^3\],y是总计算时间，a是硬件速度，x ...

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

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

nyy

灵树 发表于 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

nyy

Factorization of a 768-bit RSA modulus

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

突然发现bing搜索结果也不错，搜索英文比烂百度烂搜狗强多了！

nyy

分享一个大整数的分解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