Shor 的算法可以考慮高斯整數嗎？

這與解決以下表達式的問題有關：

X2+是2$$ x^{2} + y^{2} $$

這可以在高斯整數上分解為

(X+一世是)(X−一世是)$$ (x + iy)(x - iy) $$

如果一個人可以分解兩個平方和並取整數部分X $ x $ 一個可以解決問題。

Shor 的算法可以在高斯整數上分解一個項嗎？更準確地說，它可以用來解決兩個平方和的問題嗎？

如鍊接問題中所述，這是算法數論中與理想因式分解相關的一個相當標準的問題（例如，它隱含在這些註釋中）。請注意，沿著這些構想的解決方案需要 Shor 算法來分解X2+是2 $ x^2+y^2 $ （將其視為高斯整數的範數——將其分解為連結註釋的第 2 步）。

連結問題也提供了解決問題的“低俗”方式，至少在n=p≡1反對4 $ n = p\equiv 1\bmod 4 $ 是素數。這（隱式）處理所有n $ n $ 雖然，通過

1. 保理n $ n $ 使用 Shor 的，
2. 分別解決每個因素的問題，然後
3. 使用Brahmagupta-Fibonacci 恆等式組合解決方案。

當然，可以通過多種方式對此進行概括，但目前尚不清楚您對目前問題感興趣的概括。一般來說，我會建議隱藏子群問題的量子復雜性，它對相關工作有一些很好的參考。

查看問題的另一種方法是求解“範數方程”ñ(一個)=X $ N(a) = x $ ， 在哪裡ñ $ N $ 是場範數問(√−1) $ \mathbb{Q}(\sqrt{-1}) $ . 使用類似於 Shor 算法的技術，這也更普遍地（數量地）完成了。例如，參見Biasse 和 Song在計算方面的工作小號 $ S $ -單位群，他們提到可用於求解範數方程ñ大號/ķ(X)=θ $ N_{L/K}(x) = \theta $ 為了θ∈ķ $ \theta\in K $ .

這就是要說的

1. 您的特殊情況很簡單，並且已經（隱含）在上一個答案中解決了，並且
2. 最近有一些相關的概括，儘管如果沒有大量的代數數論，它們很難描述。也許最簡單的概括是求解範數方程ñ大號/ķ(X)=θ $ N_{L/K}(x) = \theta $ ，這可以使用 Biasse 和 Song 最近的工作使用類似 Shor 的技術來完成。

引用自：https://crypto.stackexchange.com/questions/99010