账号 自动登录 找回密码 密码 欢迎注册
 搜索

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

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

×
2^727-1=7060034896770543742372772105511569658378384779628943811708504827156734\
5759029962497646848024880749924272446637457099914453082421646959773690\
6638272121736526607699022870679030143158018123175881930939339869708632\
591433727

17606291711815434037934881872331611670777491166445300472749449436575622328171096762265466521858927

40099499726183758517891939428601665707063794593443940689888526556802581529262728143398959743444150539520890742947533452401

楼主| 发表于 2020-7-27 14:10:23 | 显示全部楼层
 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

楼主| 发表于 2020-11-2 14:33:13 | 显示全部楼层
 .·.·. 发表于 2020-7-29 23:02 https://www.mersenne.org/report_factors/?dispdate=1&exp_hi=2000 忘记最小的未分解的梅森数该怎么 ... 气宗！ 人类真的是非常有智慧的动物，能发现那么大的因子，

 .·.·. 发表于 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

 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距离被完全分解也不远了！

 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

 RSA, integer factorization, record computations https://members.loria.fr/AGuille ... g/21-MIT-RSA240.pdf

 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

 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

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2023-11-30 05:38 , Processed in 0.071417 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.