分享一个大整数的分解2^727-1

mathematica

2^727-1=7060034896770543742372772105511569658378384779628943811708504827156734\
5759029962497646848024880749924272446637457099914453082421646959773690\
6638272121736526607699022870679030143158018123175881930939339869708632\
591433727
一共219位的整数

其中一个素数因子：

17606291711815434037934881872331611670777491166445300472749449436575622328171096762265466521858927
是98位的整数
另外一个素数因子
40099499726183758517891939428601665707063794593443940689888526556802581529262728143398959743444150539520890742947533452401
是122位的素数

经过mathematica判定都是素数！

梅森数

mathematica

Lattice Siever, Mersenne Number (2^727)-1
Dear Lattice Siever,

This is a project that breaks a 219-digit number, using the Special Number Field Sieve (SNFS). This specific Mersenne number, M727, is the smallest Mersenne number (with prime exponent) for which there is no known prime factor. We know that M727 is composite by the Lucas-Lehmer test, used to find Mersenne primes (in the Great Internet Mersenne Prime Search, www.mersenne.org, for example). But a very extensive effort to find small factors, estimated to be sufficient to find an average prime factor with 50-digits, was unsuccessful. The program collects data used to build a large matrix, precisely the same method used to break RSA-keys. Building and solving the matrix problem for M727 provides a test of the methods used to break RSA-keys, and is roughly as hard as breaking an RSA-key with 460-bits (140-digits, such as RSA-140).

This calculation was not distributed.
https://www.lehigh.edu/~bad0/mer727.html

.·.·.

mathematica 发表于 2020-7-27 14:10
Lattice Siever, Mersenne Number (2^727)-1
Dear Lattice Siever,

https://www.mersenne.org/report_ ... e=1&exp_hi=2000

忘记最小的未分解的梅森数该怎么搜索了

补充内容 (2020-10-28 15:57):
2^1277-1尚无因子，最小未完全分解的梅森素数应该是2^1213-1，但最好分解的可能是2^1217-1

mathematica

.·.·. 发表于 2020-7-29 23:02
https://www.mersenne.org/report_factors/?dispdate=1&exp_hi=2000

忘记最小的未分解的梅森数该怎么 ...

气宗！
人类真的是非常有智慧的动物，能发现那么大的因子，

nyy

.·.·. 发表于 2020-7-29 23:02
https://www.mersenne.org/report_factors/?dispdate=1&exp_hi=2000

忘记最小的未分解的梅森数该怎么 ...

2^1277-1尚无因子，最小未完全分解的梅森素数应该是2^1213-1，但最好分解的可能是2^1217-1
M1213对应的合数因子是297位
M1217对应的合数因子是248位，难怪你说后者更好分解。

http://factordb.com/index.php?query=2%5E1213-1
http://factordb.com/index.php?query=2%5E1217-1

nyy

The team of computer scientists from France and the United States set a new record by factoring the largest integer of this form to date, the RSA-250 cryptographic challenge. This integer is the product of two prime numbers, each with 125 decimal digits. In total, it took 2700 years of running powerful computer cores to carry out the computation, which was done on tens of thousands of machines around the world over the course of a few months.

https://cse.ucsd.edu/about/news/ ... tographic-challenge

Mar 12, 2020
Nadia Heninger
San Diego, Calif., March 11, 2020 -- An international team of computer scientists has set a new record for integer factorization, one of the most important computational problems underlying the security of nearly all public-key cryptography currently used today

RSA-250都被分解了，看来M1217距离被完全分解也不远了！

nyy

Date: February 28, 2020

For the past three months, ever since the DLP-240 record announced in
December 2019 [1], we have been in a historically unique state of
affairs: the discrete logarithm record (in a prime field) has been
larger than the integer factorization record. We are pleased to
rectify this situation with the factorization of RSA-250 from the RSA
challenge list:

RSA-250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937
        = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
        * 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

This computation was performed with the Number Field Sieve algorithm,
using the open-source CADO-NFS software [2].

The total computation time was roughly 2700 core-years, using Intel Xeon
Gold 6130 CPUs as a reference (2.1GHz):

    RSA-250 sieving:  2450 physical core-years
    RSA-250 matrix:    250 physical core-years

Here are the factors of p+/-1 and q+/-1:

p-1 = 2 * 6213239 * 101910617047160921359 * 4597395223158209096147 * p77
p+1 = 2^3 * 3 * 7 * 223 * 587131 * 6071858568668069951281 * p93
q-1 = 2 * 5 * 13 * 440117350342384303 * 8015381692860102796237 * p83
q+1 = 2^3 * 3^3 * 23 * 2531 * 11171 * 2100953 * p108

We used computer resources of the Grid'5000 experimental testbed in
France (INRIA, CNRS, and partner institutions) [3], of the EXPLOR
computing center at Universite de Lorraine, Nancy, France [4], an
allocation of computing hours on the PRACE research infrastructure using
resources at the Juelich supercomputing center in Germany [5], as well as
computer equipment gifted by Cisco Systems, Inc. at UCSD.

We would like to dedicate this computation to Peter L. Montgomery, who
passed away on February 18, 2020.

Fabrice Boudot, Education Nationale and Universite de Limoges, France
Pierrick Gaudry, CNRS, Nancy, France
Aurore Guillevic, INRIA, Nancy, France
Nadia Heninger, University of California, San Diego, United States
Emmanuel Thome, INRIA, Nancy, France
Paul Zimmermann, INRIA, Nancy, France

[1] https://caramba.loria.fr/dlp240-rsa240.txt
[2] http://cado-nfs.gforge.inria.fr/
[3] https://www.grid5000.fr
[4] http://explor.univ-lorraine.fr/
[5] http://www.prace-ri.eu/prace-in-a-few-words/

https://listserv.nodak.edu/cgi-b ... RTHRY;dc42ccd1.2002

nyy

RSA, integer factorization, record computations

https://members.loria.fr/AGuille ... g/21-MIT-RSA240.pdf

nyy

Factoring RSA-250 with PRACE
Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger,
Emmanuel Thomé, Paul Zimmermann
November 16, 2021, CaSToRC HPC
https://members.loria.fr/PZimmermann/talks/rsa250-prace.pdf

nyy

Besides the task of factoring M1277 having (as already indicated) previously been discussed at length on the Forum (and there are several threads), there are other "holes" in the factor tables that can be filled.

My information may be a bit out of date, but as of the last time I bothered checking, of the Mp with prime exponents p < 1277,

M1213 had a C297 factor, M1217 had a C248 cofactor, M1229 had a C284 cofactor, M1231 had a C329 cofactor, M1231 a C303 cofactor, M1249 had a C326 cofactor, and M1259 had a C309 cofactor.

Some Mn with composite exponents n < 1277 also have composite cofactors. The smallest of these was n = 1207 = 17*71; M1207 had a C337 "primitive part."
https://mersenneforum.org/showpost.php?p=625313&postcount=114