最小的还没被分解的梅森合数M1277
本帖最后由 nyy 于 2023-4-12 15:05 编辑PrimeQ
这个数，肯定是一个合数。
但是只知道是合数，没有给出任何因子！
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/showthread.php?t=23280&highlight=1277
本帖最后由 灵树 于 2023-4-12 18:02 编辑
\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271 灵树 发表于 2023-4-12 17:58
\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918 ...
385位整数，估计过不了多少年就分解了！
估计是两个素数或者三个素数的乘积，
四个素数的乘积可能性不大！
五个估计就是胡扯！ 梅森数M1061分解报告
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=18631&fromuid=14149
2^1061-1=P143*P177
这是一个320位的大合数
被分解成了两个素数
灵树 发表于 2023-4-12 17:58
\(super(2^{1277}-1)\)
=2601983048666099770481310081841021384653815561816676201329778087600902014918 ...
Clear["Global`*"];(*清除所有变量*)
n=2^1277-1
r=PowerMod(*如果n是素数,那么3^(n-1)=1(mod n)*)
If]
这个整数是
2601983048666099770481310081841021384653815561816676201329778087600902\
0149183400745030598604330810462106054034885702519478458915620808662270\
3497665141933019073103237734730508644329583741539588761823985513692245\
2802923419286887119716740625346109565072933087221327790207134604146257\
0639011665562079727297004617670555507851302566746088721832395072195127\
17434046725178680177638925792182271
3^(n-1) mod n等于
1996918483046192319418122671585765807718685366219813077922752650677677\
9512676029862611571000323448537136431958018953815203841620633009240830\
7743662806783988118840125641694946643656661146859555511032219018822768\
4871208684545734968898994412714940405294059254336336551040601253189846\
8569119087415292543381643175741203010905029856987474463873997016126136\
05350163144326174904132157662013184
根据费马小定理，n一定是合数！
有没有一种算法可以估算出分解一个这样的数需要多长时间，比如：\,y是总计算时间，a是硬件速度，x是数据位数。 灵树 发表于 2023-4-16 10:53
有没有一种算法可以估算出分解一个这样的数需要多长时间，比如：\,y是总计算时间，a是硬件速度，x ...
https://www.mersenne.org/report_exponent/?exp_lo=1277&full=1
这个是对找小因子的尝试，结果都失败了！ 灵树 发表于 2023-4-16 10:53
有没有一种算法可以估算出分解一个这样的数需要多长时间，比如：\,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/showpost.php?p=486010&postcount=10
这儿说了，光是矩阵，大概就520百万行（文中没说，也可能是列）。
Filtering was performed using the MSIEVE software library . 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.php?mod=viewthread&tid=18631&highlight=1061
Factorization of a 768-bit RSA modulus
https://hal.inria.fr/file/index/docid/444693/filename/rsa768.pdf
突然发现bing搜索结果也不错，搜索英文比烂百度烂搜狗强多了！
本帖最后由 nyy 于 2023-4-18 09:16 编辑
分享一个大整数的分解2^727-1
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=17373&fromuid=14149
P98*P122=C219=M727
分享一个594位的大整数完全分解
10^593+1=11*P73*P520
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15774&fromuid=14149
页:
[1]
2