rsa - Wolfram 可以分解 300 位 RSA 号码吗？

Question

每个人都知道很难分解超过 100 位的公钥，但是250 位的 RSA 号码已经被分解，并且 Wolfram 能够分解一个 300 位的号码。

I tried factorizing public key n=144965985551789672595298753480434206198100243703843869912732139769072770813192027176664780173715597401753521552885189279272665054124083640424760144394629798590902883058370807005114592169348977123961322905036962506399782515793487504942876237605818689905761084423626547637902556832944887103223814087385426838463 using a simple prime factor program but it has encountered an error and it keeps repeating.

import math
i = 0 n=144965985551789672595298753480434206198100243703843869912732139769072770813192027176664780173715597401753521552885189279272665054124083640424760144394629798590902883058370807005114592169348977123961322905036962506399782515793487504942876237605818689905761084423626547637902556832944887103223814087385426838463

    p = math.floor(math.sqrt(n))
    while n % p != 0:
        p -= 1
        i += 1
        q = int(n / p)
        print( p,q)

结果如下：

接下来我尝试了埃拉托色尼筛法

import time
import math

def sieve(b):
global prime_list
for a in prime_list:
    if (a % prime_list[b] == 0 and a != prime_list[b]):
        prime_list.remove(a)

inp = 144965985551789672595298753480434206198100243703843869912732139769072770813192027176664780173715597401753521552885189279272665054124083640424760144394629798590902883058370807005114592169348977123961322905036962506399782515793487504942876237605818689905761084423626547637902556832944887103223814087385426838463

prime_list = []
i = 2
b = 0 
t = time.time()

while i <= int(inp):
prime_list.append(i)
i += 1
while b < len(prime_list):
sieve(b)
b += 1

print(prime_list)
print("length of list: " + str(len(prime_list)))
print("time took: " + str((time.time()-t)))

那也行不通。但是，我相信可以考虑 300 位数字。我只是不明白为什么这么多轻易放弃的程序员说这是不可能的。

标签： rsasieve-of-eratosthenes

Answer 1

如果因子很小，则更容易对数字进行因子分解。这是一个不错的 300 位大数字：

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

很明显这些因素是什么，对吧？主要因素是 2 ²⁹⁹ 5 ²⁹⁹，从数字上看应该很明显。

因此，有些数字比其他数字更容易分解。

RSA 密钥是由两个大素数相乘而成的，没有小因数。对于 309 位数字，每个因子可能超过 150 位。因此，如果您尝试使用 Eratosthenes 筛来分解一个大素数，那么您的程序将尝试计算最多 150 位的所有素数，而这实在是太多的素数无法计算。

少于 150 位的素数的个数是：

大约 10 ¹⁴⁷，因此您的程序至少需要那么多处理器周期才能完成。这个数字是如此之大，以至于如果我们使用全世界所有的计算机（可能每秒 10 ²¹或 10 ²²次操作），您的程序将需要超过 10 ¹¹⁷年才能运行（再次，使用所有计算机整个世界）。

我只是不明白为什么这么多轻易放弃的程序员说这是不可能的。

这是因为众所周知，因数分解是一个非常困难的问题——放弃的人正在放弃，因为他们知道最先进的算法用于分解大数（通用数域筛），并且知道 300 位数只是如果没有算法、计算机或工程方面的某种彻底的新发展，这是不可行的。