Shor 的算法可以考慮有限域/環/組嗎？
Shor 算法可以（有效地）求解以下形式的方程：
n=pq$$ n = pq $$
和
n=X2+是2$$ n = x^{2} + y^{2} $$
這個問題很簡單：當使用有限算術而不是整數執行這些方程時，Shor 的算法能否在多項式時間內求解這些方程？IE
n=pq反對ķ$$ n = pq \bmod k $$
和
n=X2+是2反對ķ$$ n = x^{2} + y^{2} \bmod k $$
條款的大小
至少在保理情況下，如果日誌2(p)=日誌2(q)=日誌2(ķ) $ \log_{2}(p) = \log_{2}(q) = \log_{2}(k) $ 那麼求解方程在理論上是不可能的，因為它基本上是一次性的。因此，出於這個問題的目的，假設日誌2(p)< =日誌2(q)<日誌2(ķ) $ \log_{2}(p) <= \log_{2}(q) < \log_{2}(k) $ . 我不清楚這個問題是否也適用於兩個平方和的情況；如有必要，可以對這些條款施加類似的限制，以防止解決方案的微小不可能性。
條款的性質
傳統上，因式分解被認為是關於半素數的。是否的性質p,q $ p, q $ （和/或X,是 $ x, y $ ) 在這種情況下有什麼不同嗎？如，是否有關係p,q,X,是 $ p, q, x, y $ 是素數或者如果它們滿足某些同餘（例如X=1反對4 $ x = 1 \bmod 4 $ )? 在整數上，這些條件很重要，它們對有限算術仍然重要嗎？
我將首先回答你的問題（它有一個相當直截了當的答案，你可能會對此感到失望），然後再討論我們認為量子電腦無法解決的問題的溫和擴展*，*這可能會讓你感興趣。
作為關於評論的快速旁注
至少在保理情況下，如果日誌2(p)=日誌2(q)=日誌2(ķ) $ \log_2(p)=\log_2(q)=\log_2(k) $ 那麼求解方程在理論上是不可能的，因為它基本上是一次性的。
通常，如何處理是說如果對手恢復任何解決方案，他們就會獲勝X2+是2反對ķ $ x^2+y^2\bmod k $ ，而不是一些特定的解決方案。這可以在諸如
- 一致的密鑰恢復遊戲（而不是目標密鑰恢復遊戲），以及
- 單向函式如何需要恢復任何原像是 $ y $ ，例如任何X $ x $ 這樣F(X)=是 $ f(x) = y $ ，而不是一些“確切的”X′ $ x’ $ 這是在遊戲過程中內部選擇的。
我將用這些術語來描述事物，因為它是標準的。如果這不適合您的應用程序，您或許應該嘗試更多地描述您的應用程序。
這個問題很簡單：當使用有限算術而不是整數執行這些方程時，Shor 的算法能否在多項式時間內求解這些方程？
我的理解是 Shor 的算法被描述了從 $ \mathbb{Z} $ 而不是從n $ \mathbb{Z}_n $ 它的“現實世界”實施並不是一個嚴重的問題。特別是，雖然確實需要注意使用的有限精度表示不會太“有損”，但我的理解是，這些細節比建構量子電腦之類的東西更容易解決。
如果這個理解是正確的，那麼這兩個問題的答案就很簡單了——求解上面的各種方程從 $ \mathbb{Z} $ ，然後減少答案反對ķ $ \bmod k $ 獲得解決方案從ķ $ \mathbb{Z}_k $ . 正如雨披在評論中指出的那樣，解決問題n=X是反對ķ $ n = xy\bmod k $ 為了X,是 $ x, y $ 甚至在經典上也很容易，所以這個故事的寓意是施加模組化約束可以使問題（也許）變得非常容易，但對於這些問題，它們不會使問題變得更難。
解決的問題有一個溫和的擴展n=X是反對ķ $ n = xy \bmod k $ 這被認為是量子困難的。求解這種一致性可以看作是求解單變數（精確）線性方程。有兩種自然的方法可以概括這一點
- 不止一個變數，並且
- 不止一個方程。
例如，將問題更改為給出的問題→b=一個→s反對ķ $ \vec b = A\vec s\bmod k $ 在哪裡→b∈從nķ,一個∈從n×nķ,→s∈從nķ $ \vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n $ . 不過，這仍然是微不足道的“解決”——如果你選擇一個 $ A $ 為單位矩陣，則→s=→b $ \vec s = \vec b $ 作品。更一般地說，如果您選擇一個 $ A $ 可逆從ķ $ \mathbb{Z}_k $ ， 然後→s=→一個−1→b $ \vec s = \vec A^{-1}\vec b $ 作品。即使→一個 $ \vec A $ 是不可逆的（比如說它是非平方的），您可以使用一般的線性代數技術來做一些事情。所有這些都是有效的，經典的，例如 Shor 的仍然是矯枉過正。
通常如何阻止上述攻擊有兩個方面
- 指定一些矩陣一個 $ A $ 一個必須使用（所以一個不能設置一個 $ A $ 是恆等式或隨機可逆矩陣），和
- 在問題中註入一些噪音。
請注意，僅第一點就足夠了（雨披的攻擊仍然有效），因此第二點應該被視為基本點。具體問題如下
學習錯誤：讓一個∈從n×nķ $ A\in\mathbb{Z}_k^{n\times n} $ 是均勻隨機的，並且讓→s∈從nķ $ \vec s\in\mathbb{Z}_k^n $ 是一個“秘密”向量。對於固定分佈χ $ \chi $ 支持從ķ $ \mathbb{Z}_k $ ，我們說有錯誤的搜尋學習問題是要恢復→s $ \vec s $ , 給定(一個,一個→s+→和) $ (A, A\vec s + \vec e) $ ， 在哪裡→和←χn $ \vec e \gets \chi^n $ .
根據參數化，LWE 問題是對量子電腦安全的硬度假設的主要候選者之一。也就是說，對於求解的一個合適的泛化n≡X是反對ķ $ n \equiv xy\bmod k $ , 認為 Shor 算法無法解決問題。如上所示，概括是從您的初始問題中刪除的許多步驟。
在這個方向上還有其他類似的概括（The Learning Parity with Noise 問題，或 Approximate GCD 問題） — 與所有這些的基本相似之處是你有一些線性問題的“嘈雜”變體。
另外還有一個概括X2+是2反對ķ $ x^2+y^2\bmod k $ 被認為是量子安全的問題，但我不知道那麼多細節，所以會少寫。粗略地，一個替換二次多項式F(X,是)=X2+是2反對ķ $ f(x, y) = x^2+y^2\bmod k $ 具有任意二次多項式（或多項式集合）n $ n $ 變數。然後就是恢復的問題(X1,…,Xn) $ (x_1,\dots, x_n) $ 是多元二次多項式的（同時）零點p0,…,p米 $ p_0, \dots,p_m $ （大致）與打破“多變數密碼系統”有關。請注意，堅持要恢復多項式的零（而不是p(X0,…,Xn)=ñ $ p(x_0,\dots,x_n) = N $ ，正如你所要求的）沒有失去一般性，因為人們可以通過查看零來恢復這一點p(X0,…,Xn)−ñ $ p(x_0,\dots,x_n) - N $ .
這就是說
- Shor 被認為可以解決你的兩個問題，但是
- 您的兩個問題都被認為是量子安全的。事實上，許多“領先的”量子安全假設（我所知道的一切，除了同源材料和等級度量編碼的東西）都可以看作是對你的問題的概括。