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

nyy

False, and false. Just because the hardware on your desk isn't sufficient, concluding the hardware does not exist is plain wrong. Software is easy: CADO is sufficient to factor it- the CADO team factored numbers of size 2^1200 already, and one can peruse their paper on those jobs to learn what hardware requirements there were at that size and then scale RAM needs for the bigger input size.

For those merely curious about scale rather than details, a sieve process might need 60-80GB of ram to run and the matrix might need a 1TB ram machine for the CADO matrix solving style, or a cluster totaling 1-1.5TB ram if using msieve for the matrix.

SNFS jobs such as 2^1277-1 double in CPU-years difficulty roughly every 30 bits, so this job would take ~8 times longer than 2^1190 (a size that has been factored already by the CADO team).

https://www.mersenneforum.org/sh ... 017&postcount=5

M1277 (SNFS 385) is very roughly 4 times as difficult as RSA-250 (GNFS 250), which took the CADO team 2700 CPU-years. So we're looking at about 10,000 CPU-years for M1277.

The hardware definitely exists. As for software, current CADO can probably handle it, but there's an upper limit of 2^31 for factor base primes, and this might add an extra thousand CPU-years or so. The CADO team have been working on extending the limit to 2^32 for a while.

https://www.mersenneforum.org/sh ... 036&postcount=9


https://www.mersenneforum.org/showthread.php?t=27835

灵树

如果是用量子计算来分解能快到什么程度，国内的量子计算一直在说已经达到多少个量子级别，不过感觉都还是很遥远的东西，能拿来分解一个才能说明问题。好象没听说谁来做过。

nyy

灵树 发表于 2023-4-18 10:08
如果是用量子计算来分解能快到什么程度，国内的量子计算一直在说已经达到多少个量子级别，不过感觉都还是很 ...

量子计算机基本就胡扯，不要相信他们的鬼话！

nyy

灵树 发表于 2023-4-18 10:08
如果是用量子计算来分解能快到什么程度，国内的量子计算一直在说已经达到多少个量子级别，不过感觉都还是很 ...

Records for efforts by quantum computers
The largest number reliably factored by Shor's algorithm is 21 which was factored in 2012.[23] 15 had previously been factored by several labs.

In April 2012, the factorization of  by a room temperature (300K) NMR adiabatic quantum computer was reported by a group led by Xinhua Peng.[24] In November 2014 it was discovered that the 2012 experiment had in fact also factored much larger numbers without knowing it.[clarification needed][25][26] In April 2016 the 18-bit number 200,099 was factored using quantum annealing on a D-Wave 2X quantum processor.[27] Shortly after, 291 311 was factored using NMR at higher than room temperature.[28] In late 2019, Zapata computing claimed to have factored 1,099,551,473,989,[29] and in 2021 released a paper describing this computation.[30]

In December 2022, the 48-bit factorisation  was completed using a 10-qubit flip-chip superconducting quantum processor by a team in China. [31] The team also factored the 11-bit integer 1961 and 26-bit integer 48567227 with 3 and 5 superconducting qubits respectively. However, the approach was described by the team as a "classical-quantum hybrid", using the quantum approximate optimization algorithm to optimize the time-consuming sr-pair generation used in Schnorr's factoring algorithm, [32] and a classical computer to solve the resulting linear equations.


As such, claims of factoring with quantum computers have however been criticized for depending heavily on classical computation to reduce the number of qubits required.[33] [34] For example, the factorization of 1,099,551,473,989 relied on classical pre-processing to reduce the problem to a three-qubit quantum circuit.[30] Furthermore, the three numbers factored in this paper (200,099, 291,311, and 1,099,551,473,989) can easily be factored using Fermat's factorization method, requiring only 3, 1, and 1 iterations of the loop respectively.

https://handwiki.org/wiki/Integer_factorization_records

这是量子计算机的记录！

灵树

量子计算路远且长！

灵树

据说Edge是用chatGPT后台翻译的，以下是翻译的结果：

量子计算机
努力的记录 Shor算法可靠分解的最大数字是21，这是2012年分解的。[23]15以前曾被几个实验室考虑过。
2012年300月，由彭新华领导的一个小组报道了室温（24K）核磁共振绝热量子计算机的分解。[2014]2012年25月，人们发现26年的实验实际上也在不知情的情况下分解了更大的数字。[需要澄清][2016][18] 200 年 099 月，2 位数字 27，291 在 D-Wave 311X 量子处理器上使用量子退火进行分解。[28]不久之后，在高于室温的情况下使用NMR对2019 1进行分解。[099]在551年底，萨帕塔计算声称已经分解了473，989，29，2021，30，[2022]，并在48年发表了一篇描述这种计算的论文。[10]
31 年 11 月，中国的一个团队使用 1961 量子位倒装芯片超导量子处理器完成了 26 位因式分解。[48567227]该团队还分解了3位整数5和32位整数33，分别具有34和1个超导量子位。然而，该方法被团队描述为“经典量子混合”，使用量子近似优化算法来优化Schnorr分解算法中使用的耗时sr对生成，[099]和经典计算机来解决产生的线性方程。
因此，使用量子计算机分解的说法受到批评，因为它严重依赖经典计算来减少所需的量子比特数量。[551] [473]例如，989，30，200，099，291的因式分解依赖于经典的预处理，将问题简化为三量子比特量子电路。[311] 此外，本文中分解的三个数字（1，099、551，473 和 989，3，1，1，<>）可以使用费马分解方法轻松分解，分别只需要循环的 <>、<> 和 <> 次迭代。

无心人

灵树 发表于 2023-4-19 18:37
据说Edge是用chatGPT后台翻译的，以下是翻译的结果：

量子计算机

50位十进制用当前千元级别手机秒出，啥时候量子计算机分解速度超过手机再说

nyy

无心人 发表于 2023-4-24 16:07
50位十进制用当前千元级别手机秒出，啥时候量子计算机分解速度超过手机再说

量子计算机要是真的成功了，估计就没啥隐私了！