#閱讀“Quantum algorithms for computing short discrete logarithms and factoring RSA integers”一文矿咕，對文章稍作一些我的見解
本文主要講的是用于計算短離散對數的廣義算法的應用师坎，包括計算短離散對數和分解RSA整數。雖然這個算法比一般分解算法復雜得多遗遵，但是它對量子計算機提出更小的要求搬味。
計算有限循環(huán)群中的短離散對數的算法是通過引入修改后的Shor算法境氢，重點是Shor算法的量子傅里葉變換。
Shor算法
在一個量子計算機上面碰纬，要分解整數N, 舒爾算法的運作需要多項式時間 (時間是log N的某個多項式這么長,log N在這里的意義是輸入的檔案長度)萍聊。 更精確的說，這個算法花費O((log N))的時間悦析，展示出質因子分解問題可以使用量子計算機以多項式時間解出寿桨，因此在復雜度類 BQP里面。
選擇任意數字a < N 計算gcd(a, N)。 這里可以使用輾轉相除法來計算亭螟。?
若 gcd(a, N) ≠ 1挡鞍，有了一個N非平凡的因子，這部份結束了预烙。
?否則墨微，利用下面的周期尋找副函式來找出下面這個函數的周期r：
?若r是奇數，回到第一步扁掸。
若ar /2 ≡ -1 (mod N), 回到第一步翘县。
gcd(ar/2 ± 1, N) 是N非平凡的一個因子。分解完成谴分。
量子部份：周期尋找副函式(Period-finding subroutine) 這個算法使用的量子線路是為了在給定一個固定常數 N 以及一個任意常數 a之下锈麸，找出f(x) = ax mod N所設定的。給定N, 找出Q = 2q且合乎(這同時表示)牺蹄。輸入和輸出量子位元暫存器需要儲存從0到Q-1所有值的疊加態(tài)忘伞，因此分別需要q個量子位元。這里使用看起來比所需的數量還要更多一倍的量子位元沙兰，保證了即使周期r的大小逼近N/2氓奈，也至少有N個不同的x會產生相同的 f(x)。
量子傅里葉變換
離散量子傅里葉變換（QFT）被用來通過建設性的干涉來實現振幅放大僧凰。
QFT將n個比特寄存器中的每個狀態(tài)映射到
所以QFT映射系統功能
計算短離散對數
計算短離散對數的廣義算法由兩個階段組成探颈， 一個初始的量子階段和一個經典的后處理階段。
初始的量子階段用量子算法描述训措，輸入g和x = [d] g得到一對（j，k）光羞。
量子算法
令m為符合0<d<2的m次方 的最小整數绩鸣，并設為接近m / s的整數。假設g的階數r至少為2 + m + 2d纱兑，本節(jié)所描述的量子算法將根據g和x = [d] g的輸入計算并輸出一對（j呀闻，k）。然后將一組這樣的對輸入到經典算法以恢復d潜慎。
其中第一和第二寄存器的長度為λ+ m和λ qubits捡多。
計算[a] g☉ [-b] x并將結果存儲在第三個寄存器中
計算第二寄存器的第一寄存器的大小為2的（λ+m）次方的QFT和第二寄存器的大小為2的λ次方的QFT以獲得
觀察系統的測量結果，得到（j铐炫，k）和[e] g垒手。
后處理階段
該算法如下進行以從{（j1，k1）倒信，...科贬，（js，ks）}選出一個d
測試u的最后一個組件是否為d鳖悠，如果是則返回d榜掌。如果找不到d或者搜索不可行优妙，則算法失敗。
根據要實現該算法的量子計算機的特定架構憎账，可能需要在實現的設計和優(yōu)化方面做出不同的選擇套硼。
算法的應用
計算短離散對數
用于計算短離散對數的量子算法可以用來攻擊依賴于該問題的計算難以處理的非對稱密碼方案的某些實例。 這樣一個應用的一個具體例子就是當安全素數組與短指數結合使用時胞皱，攻擊Diffi-Hellman超過有限域熟菲。 在選擇和比較依賴于離散對數問題的計算難解性的非對稱密碼方案的域參數時，應當考慮到計算量子計算機上短離散對數的有效專用算法的存在朴恳。
分解RSA整數
設G是階次r的循環(huán)群抄罕。 令r0是一個已知的近似值，使得0≤r-r0 <2m于颖。 在邊信息r0下計算階數r的問題然后可以被重新設計為一個短離散對數問題： 1.設g是G的一個生成元呆贿。計算x = g-r0。 那么x≡gr-r0森渐。 2.從g和x計算短離散對數d = r-r0做入。 3.計算順序r = d + r0 。
題外話
量子計算機的最核心的是來自于相干性同衣。這個是物理層面上的竟块，經典的計算機是永遠也不可能有這種相干性的。相干性有了superposition耐齐，這就導致了物理意義上的同時對不同態(tài)的運算浪秘。但是由于技術等原因，量子計算機還有很多需要突破的問題埠况。而本文提到的算法對量子計算機提出了更小的要求耸携，對于量子計算機今后的有關發(fā)展提出了建設性的想法。
將因式分解問題重寫為短離散對數問題辕翰，并使用算法計算短離散對數夺衍，從而得到兩個因子。 有一種方法可以看出喜命，我們知道φ（N）的近似值N. 這給了我們一個短的離散對數問題沟沙，該求解算法不需要事先知道這個順序。
因為構建和運行龐大而復雜的量子計算機似乎很困難壁榕。 如果一個量子算法的復雜度可能會降低矛紫，那么就量子計算機的要求而言，這很可能意味著能夠執(zhí)行算法和不能執(zhí)行該算法之間的差異护桦。在硬件方面仍需不斷進步去支持該算法的實現含衔。實現該算法的量子計算機的特定架構，可能需要在實現的設計和優(yōu)化方面做出不同的選擇。
鄙人不才贪染，有錯誤請輕踩缓呛。
