找回密码
 欢迎注册
查看: 9142|回复: 10

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

[复制链接]
发表于 2020-7-27 14:08:45 | 显示全部楼层 |阅读模式

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

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

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

其中一个素数因子:

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

经过mathematica判定都是素数!

梅森数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-7-29 23:02:12 | 显示全部楼层
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

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

气宗!
人类真的是非常有智慧的动物,能发现那么大的因子,
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-18 09:43:28 | 显示全部楼层
.·.·. 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 09:17:56 | 显示全部楼层
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距离被完全分解也不远了!

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 09:20:40 | 显示全部楼层
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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 09:29:03 | 显示全部楼层
RSA, integer factorization, record computations

https://members.loria.fr/AGuille ... g/21-MIT-RSA240.pdf
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 09:33:32 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-28 13:37:05 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-6-13 05:20 , Processed in 0.047278 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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