從數學上/理論上計算時間來暴力破解量子電腦與經典電腦的 RSA 加密密鑰？
- 理論上有沒有辦法通過使用數學來計算暴力破解 RSA 密鑰所需的時間？
我知道有一種方法可以使用經典電腦和暴力破解 RSA 密鑰所花費的時間，但我想具體了解如何計算時間。
此外，由於使用量子電腦暴力破解 RSA 密鑰的技術與經典電腦的技術不同；如何計算使用量子電腦暴力破解 RSA 密鑰的時間？
- 要進行計算，我猜您必須考慮計算能力。如果可能的話，使用（或給我一個例子）經典電腦和量子電腦之間的相等（ish）計算能力。例如，就暴力破解 RSA 密鑰而言，與 5 量子位量子電腦（僅）比較（並處於同一水平）需要多大規模的經典電腦？
理論上有沒有辦法通過使用數學來計算暴力破解 RSA 密鑰所需的時間？
即使是經典的，這也並不像你所暗示的那麼容易。
RSA 基於整數分解問題的難度。已知最快的解決此問題的經典算法是通用數域篩(GNFS)，它在次指數時間內解決整數分解，或 $ \exp((\sqrt[3]{64/9}+o(1)) (\log N)^{1/3} (\log \log N)^{2/3}) $ 在哪裡 $ N $ 是模數，並且 $ \log $ 指自然對數。
但是，我們無法使用此公式輕鬆計算出準確的執行時間。漸近執行時間隱藏了常數值，該常數值可能因算法而異。此外，他們沒有告訴我們任何可能的並行化。
GNFS 恰好是一個非常複雜的算法。它涉及大量參數。該算法有四個不同的“階段”。可以使某些階段花費更多時間，以使其他階段更快。此外，一些階段很容易並行化，而其他階段則不是，或者僅在有限的程度上。換句話說，提出正確的參數集以最小化破壞 RSA 模數的總時間絕非易事。更不用說稍微準確地估計需要多少時間了。
所以不幸的是，這個問題沒有簡單的答案。但是，您可以通過查看一些已成功分解的數字來獲得一個想法。
如何計算使用量子電腦暴力破解 RSA 密鑰的時間？
這更容易計算，但同時也是不可能的。整數分解可以在量子電腦上使用Shor 算法完成。該算法在多項式時間內執行， $ O((\log N)^2 (\log \log N) (\log \log \log N)) $ . 從這篇論文中可以看出，所需的邏輯量子比特數大約為 $ 2 \log N $ ，以及邏輯量子門的數量 $ 4(\log N)^3 $ .
正如論文中提到的，這些邏輯量子位和量子門需要許多物理量子位和量子門才能真正實現。由於量子退相干的問題，目前還不確定量子計算是否可以大規模進行。再說一次，恐怕這個問題沒有答案。你怎麼可能估計算法在還不存在的電腦上的執行時間？