Shor 的因式分解算法和 Shor 的對數算法有什麼區別？
Peter W. Shor 於 1994 年發表了一篇論文： Algorithms for Quantum Computation: Discrete Logarithms and Factoring，我對它和提出的算法有疑問。
對於整數分解問題，Shor 算法可作為函式 的快速週期查找器
f(x) = a^x mod N，其中半素數 N 等於 p*q，a 是固定的，並且所有可能的指數x都是量子計算的。然後，Shor 使用 Simon 算法找到這樣的周期r。以 0.5 的機率，量子方案的輸出將是偶數，並且將是 的非平凡平方根。有了這樣的根，我們可以很容易地破解到and 。（如果這個描述有問題，請評論。簡單的量子電路在 這裡。f(x)``f(x) = f(x+r)``r``a^(r/2)``1 mod N``N``p``q但是 Shor 的離散對數問題算法是如何工作的呢？只有素數
P（和生成器g），所以我們不能把它分解成具有平方根的東西。我什至不確定該領域是否會有任何重要的平方根mod p。離散對數的任務是：給定一些
x，等於x = g^r mod p，已知 ，g找到。p``r
事實上，針對離散對數問題的 Shor 算法的基本思想相當簡單。
假設（如第 4 節離散對數： Shor 論文的簡單案例）你有一個有效的傅里葉變換量子算法。然後，應用此傅里葉變換兩次（一次用於 $ a $ 一次 $ b $ ) 值的量子疊加 $ g^a\cdot x^{-b} $ 和測量產生一對 $ (c,d) $ 和 $ d\equiv -cr\pmod{p-1} $ . 因此，您可以恢復 $ r $ （如果gcd的 $ c $ 和 $ p-1 $ 是 $ 1 $ ) 直接用簡單的除法取模 $ p-1 $ . [如果gcd是一個小數字也很容易得出結論]
不幸的是，直接做這個傅里葉變換只有在 $ p-1 $ 是平滑的（這是一個無趣的情況，因為在這種情況下使用經典電腦很容易使用 dlogs）並且因此出現技術性問題。這些技術細節涉及替換傅里葉變換模 $ p-1 $ 通過傅里葉變換模 $ q, $ 在哪裡 $ q $ 很光滑，距離不太遠 $ p-1 $ . 類似的技術用於因式分解：它比一般的離散對數情況更簡單，因為在這種情況下，傅里葉變換的單個應用就足夠了。