以目前的數論水平，計算機運算速度需要達到什麼數量級才有可能破解RSA演算法？

12-29

曾有過4096位RSA演算法被破解過，但是並非完全是『技術層面』的。相關報道：Researchers crack the world』s toughest encryption by listening to the tiny sounds made by your computer』s CPU

想知道如果數論方面沒有突破性進展，那麼想破解RSA演算法，計算機運算速度需要達到什麼數量級？

目前已知最快的公開演算法是：General number field sieve

其heuristic的複雜度為：（猜想）

這是亞指數級的。

但是number field sieve比較難以實現（因為涉及到computational algebraic number theory中的一些演算法），而且在位數較小的時候和其它的演算法（比如Quadratic sieve之類）比並沒有優勢。

這裡：RSA numbers，有關於整數分解的一些結果。其中RSA1024和RSA2048都有懸賞。

這裡有一個實現了Quadratic seive的程序：Msieve | SourceForge.net

不過題主這裡提到的RSA問題並不完全等價為大數分解問題，一般猜想RSA問題要弱於大數分解問題。[5]

關於RSA問題的攻擊方法也有很多，比如連分數方法[4]、基於格的方法[3]等。

====
樓下匿名用戶提到了shor演算法[2]，事實上如果允許使用圖靈機以外的計算模型，那麼用DNA計算機就可以解決所有的NP問題（這當然包括大數分解）。[1]

Reference
[1]. https://books.google.com.hk/books?id=r9K-ZsmP1qUCpg=PA50lpg=PA50dq=Lipton+3sat+dna+computationsource=blots=C9tHttDTYfsig=trZyxJjemZAJN0ZY6mzs9HZmUtghl=ensa=Xei=aYUaVZK7CsS_ggSF5IOwCQved=0CE0Q6AEwCQ#v=onepageq=Lipton%203sat%20dna%20computationf=false
[2]. http://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes11.pdf
[3]. Lattice based attack. Coppersmith"s Attack
[4]. Continued fraction based attack. Wiener"s attack
[5]. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

shor演算法，可以在多項式的時間內在量子計算機上解決。

如果沒理解錯的話，你引用的那篇論文採用的側信道攻擊。所謂側信道攻擊的確沒有從演算法層面攻擊rsa本身，但是可以利用密碼體制在人為實現中的系統能量消耗，比如不可避免的熱量散發，硬碟讀寫，聲音等，獲取該密碼實現的參數。而你問的是計算複雜度的問題。以現在的計算能力，用再牛逼的篩法，也無法破解4096位的。

impossible

破解RSA又不是一個不可計算問題，所以任何計算機都可以用來破解RSA，只是效率的問題。這樣回答算不算耍流氓？其實題主是想問如何有效的破解RSA。那麼什麼是有效？自行參考計算複雜度的一切。
至於現有攻擊方法，目前最有效的應該是Shor"s algorithm，基於量子傅里葉變換的量子演算法。