什麼是Shor 演算法
以量子傅立葉轉換求出週期，在多項式時間內解出大整數質因數分解與離散對數問題的量子演算法。由彼得·秀爾於 1994 年發表。可以破解 RSA 與橢圓曲線密碼，但執行時需要大規模的容錯量子電腦。
日文名稱: ショアのアルゴリズム
「Shor 演算法」出現在1領域的4道練習題中（量子電腦硬體等）。
這個名詞所屬的領域: 量子電腦硬體
練習Shor 演算法的題目
大規模容錯量子電腦實現時，一般認為安全性會因 Shor 演算法而大幅受損的密碼是下列何者？
- ARSA 與橢圓曲線密碼等公開金鑰加密
- B只有 AES 等對稱式加密
- C一次性密碼本（以只用一次的隨機金鑰加密的方式）
2020 年代中期的量子電腦無法以 Shor 演算法破解 RSA-2048，其主要理由最適當的是下列何者？
- AShor 演算法在量子位元數量超過 1,000 個時，原理上就無法運作
- B已有數學證明，破解 RSA-2048 時古典電腦比較快
- C必須無錯誤地執行非常大量的邏輯閘，需要由錯誤更正建構的大量邏輯量子位元，以及支撐它們的龐大數量物理量子位元
查看答案與解析
正確答案：C. 必須無錯誤地執行非常大量的邏輯閘，需要由錯誤更正建構的大量邏輯量子位元，以及支撐它們的龐大數量物理量子位元
破解 RSA-2048 需要在約一千到數千個邏輯量子位元上，連續執行數十億次規模的邏輯閘。因此邏輯錯誤率必須極低，為了錯誤更正，每個邏輯量子位元需要數百個以上的物理量子位元。2020 年代的估算認為，需要錯誤率約 0.1% 的物理量子位元數十萬到數千萬個（數字隨前提條件而有很大差異），與目前裝置的規模相差好幾個數量級。不過，所需規模的估算隨著演算法的改良而逐漸變小，因此密碼遷移的準備需要及早進行。
解析中的「Shor 演算法」
Shor 演算法利用量子傅立葉轉換求出週期，能在多項式時間內解出這些問題。
大規模容錯量子電腦實現時，一般認為安全性會因 Shor 演算法而大幅受損的密碼是下列何者？加速只有平方的程度，不像 Shor 演算法那樣有指數性的差異。
從排列沒有規則的 100 萬筆資料中尋找符合條件的 1 筆時，Grover 演算法所需的查詢（呼叫預言機）次數的數量級…後量子密碼以格問題、雜湊函數等為基礎，取代會被 Shor 演算法解出的質因數分解與離散對數問題，並且可直接在現有的電腦與網路設備上運作。
關於後量子密碼（PQC），下列敘述何者正確？