文章主要思想與工作
本文的主要思想是實施后量子RSA算法浴讯。對RSA參數(shù)的密鑰生成，加密蔼啦，解密榆纽，簽名和驗證的過程，在現(xiàn)在的計算機里是可行的捏肢，即使是在高度可擴展的量子計算機奈籽。為了提供后量子RSA算法的初始實驗結(jié)果，本文提出了新的素數(shù)生成算法和量子分解算法鸵赫，分別作為性能分析和攻擊分析的部分衣屏。新的量子分解算法要比Shor算法和量子分解算法要快得多。
相關(guān)技術(shù)
Shor算法
選擇任意數(shù)字a < N
計算gcd(a, N)辩棒。 這里可以使用輾轉(zhuǎn)相除法來計算狼忱。
若 gcd(a, N) ≠ 1膨疏，則我們有了一個N非平凡的因子，因此這部份結(jié)束了钻弄。
否則佃却，利用下面的周期尋找副函式(Period-finding subroutine，下面會列出)來找出下面這個函數(shù)的周期r： ,換句話說窘俺，找出在里面的目饲帅，或者最小的正整數(shù)r令 。若r是奇數(shù)瘤泪，回到第一步灶泵。若ar /2 ≡ -1 (mod N), 回到第一步。gcd(ar/2 ± 1, N) 是N非平凡的一個因子对途。分解完成赦邻。
量子部份：周期尋找副函式(Period-finding subroutine)
這個算法使用的量子線路是為了在給定一個固定常數(shù) N 以及一個任意常數(shù) a之下，找出f(x) = ax mod N所設(shè)定的掀宋。給定N, 找出Q = 2q且合乎(這同時表示)深纲。輸入和輸出量子位元暫存器需要儲存從0到Q-1所有值的疊加態(tài)仲锄，因此分別需要q個量子位元劲妙。這里使用看起來比所需的數(shù)量還要更多一倍的量子位元，保證了即使周期r的大小逼近N/2儒喊，也至少有N個不同的x會產(chǎn)生相同的 f(x)镣奋。
Grover算法
它適用于解決如下問題：從 N個未分類的客體中尋找出某個特定的客體。經(jīng)典算法只能是一個接一個地搜尋怀愧，直到找到所要的客體為止侨颈，這種算法平均地講要尋找 N／2次，成功幾率為1／2,而采用Grover的量子算法則只需要 Nkk√次芯义。例如哈垢，要從有著100萬個號碼的電話本中找出某個指定號碼，該電話本是以姓名為順序編排的扛拨。經(jīng)典方法是一個個找耘分，平均要找50萬次，才能以 1／2幾率找到所要電話號碼绑警。 G rover的量子算法是每查詢一次可以同時檢查所有100萬個號碼求泰。由于100萬量子比特處于疊加態(tài)，量子干涉的效應(yīng)會使前次的結(jié)果影響到下一次的量子操作计盒，這種干涉生成的操作運算重復(fù)1000（即 N √）次后渴频，獲得正確答案的幾率為1／2。但若再多重復(fù)操作幾次北启，那么找到所需電話號碼的幾率接近于1卜朗。
相關(guān)算法
Shor算法
Grover算法
未來的研究方向拔第，未解決的難題：
Product Tree產(chǎn)生一個“虛擬鍵”，一個隨機的4096位整數(shù)的1TB產(chǎn)品聊替。經(jīng)過性能統(tǒng)計楼肪，本產(chǎn)品計算出每個CPU的指令周期（IPC）的命令，周期-睡眠測量引起的交換會產(chǎn)生損失惹悄。當(dāng)沒有交換發(fā)生時春叫，機器每周期大約有2條指令，但是在交換時泣港，每個周期的指令每周期會減少0.37指令暂殖，每個周期大約有0.5到1.2條指令。若盡可能地在交換時減少指令的損失当纱，效果可以更好呛每。
