量子電腦

前幾天有講到RSA是利用質因數分解困難的性質來設計

回憶先前的內容：
目前為止，沒有任何演算法被找到，也沒有證明不存在，可以在多項式時間內分解所有整數的演算法

根據維基百科上大數分解的紀錄，在2020年，利用幾百多台Intel Xeon Gold 6130 CPU跑了總共2700個CPU-年(意思是只用一顆CPU開著跑不眠不休要跑2700年)，分解一個叫RSA-250的829位元的250位數

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937 = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367 * 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

即使用世界最頂尖的電腦以及最猛的演算法也得花上那麼久的時間解829位元的數，可想而知現行的RSA用更大的3072位元等級根本無法被計算出來

既然昨天都有提到一點物理了，那麼就順便談一下量子電腦在這方面會有什麼突破

量子世界與巨觀世界的物理相當不同
我們都有聽過薛丁格的貓的比喻，指的就是量子狀態能夠呈現類似生與死同時疊加的事情，而該特性可以讓我們設計出傳統電腦(相較於量子電腦傳統)無法辦到的演算法

傳統電腦的位元儲存只有0和1兩種狀態，而量子電腦利用狀態可疊加的特性，其單一位元紀錄多少比例在狀態0，多少比例在狀態1
在尚未被量測之前，我們無法得知該位元究竟是在0還是1
正因為此疊加特性，讓一量子位元的儲存資訊比一傳統位元能儲存的資訊豐富非常多
其運算的規則皆被量子力學的物理定律所掌管

在1994年，Shor設計出了一個能夠快速分解整數的量子演算法，該演算法可以在比多項式時間還要快的情況下完成任何整數的分解

也就是說，利用量子電腦搭配Shor演算法，質因數分解便不再是個難題，RSA加密即可輕易破解
Shor演算法的變種也可解決輕鬆算出離散對數問題，因此前面介紹的DH對稱密鑰分享也變得十分脆弱

要讀懂Shor演算法不難，各位有興趣的可以參考這本量子計算的經典

不過也正是因為量子位元的反直覺，讓演算法開發的過程相當困難，也因此目前人們開發出能夠超越傳統演算法的量子演算法十分稀少

話說回來，雖然量子電腦聽起來很厲害，但是目前量子特性只有在極精密的實驗室中方能顯現
依據紀錄，真正在實驗室用Shor演算法算出來的最大數字是21
其他也有用量子電腦分解很大數的例子，不過都不是用真正的Shor演算法完成

要能夠真正超越RSA，甚至普及至一般家戶，或許是幾百年後的事了