顯示FACTORING≤PSQROOTFACTORING≤PSQROOTtext{FACTORING} le_P text{SQROOT}
我試圖證明 $ \text{FACTORING} \le_P \text{SQROOT} $ 在一般情況下，所以 $ n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} $ .
定理：讓 $ n $ 是一個合數並讓 $ x $ 和 $ y $ 是整數，使得 $ x^2 \equiv y^2 \pmod n $ 和 $ x \not \equiv \pm y \pmod n $ 持有。然後 $ \gcd(x+y, n) $ 和 $ \gcd(x-y, n) $ 是的非平凡除數 $ n $ .
我的嘗試：
$ \text{FACTORING} \le_P \text{SQROOT} $ : 假設我們有一個算法 $ \mathcal{A} $ 解決了 $ \text{SQROOT} $ . 我們表明我們可以考慮 $ n $ 帶質因數分解 $ n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} $ . 隨機選擇 $ x \in Z/nZ $ 和 $ \gcd(x,n) = 1 $ . 計算 $ a = x^2 \pmod n $ 並使用 $ \mathcal{A} $ 求平方根 $ y $ 的 $ a $ 模組 $ n $ . 如果 $ y \equiv \pm x \pmod n $ 選擇另一個 $ x $ 並重複這個過程，直到 $ y $ 和 $ y \not \equiv \pm x \pmod n $ 被發現。既然有 $ 2^k $ 不同的平方根 $ a $ 模組 $ n $ 需要重複上述程序的機會是 $ \frac{1}{2^{k-1}} $ . 所以通過上面的定理我們可以找到兩個非平凡的除數 $ n $ 在預期的多項式時間內。對由此找到的因子重複此過程 $ n $ 我們可以找到素數分解 $ n $ 在預期的多項式時間內。
我對整個“預期多項式時間”的事情有點不確定。到目前為止，我只聽說過它的非正式定義。你能看看我的證明嗎？
編輯：我最初接受了下面 Meir Maor 的答案，但我剛剛意識到，其中有一個差距：
$ k=2 $ 是最壞的情況。但這僅意味著 $ n=p_1^{\alpha_1}p_2^{\alpha_2} $ ， 不是 $ n=p_1 p_2 $ . 因此，我們仍然需要找到由此找到的因子的一些非平凡除數 $ n $ 要得到 $ p_1 $ 和 $ p_2 $ . 我想保持 Meir Maor 回答的嚴謹性，但我不知道如何確定此過程的執行時間。你可以幫幫我嗎？
你的證明基本上是正確的。您可以通過精確計算或限制其預期執行時間來提高嚴謹性。
如果我們採用 k=2 的簡單情況（也是最壞的情況），我們得到 1/2 的機率得到不同的根。
應該注意的是，由於我們的根 x 在 Z/nZ 上是均勻隨機的，所以它在 a 的根上也是均勻隨機的。因此，無論我們的 SQROOT 算法如何選擇提供哪個根，每次嘗試的成功機率都是 1/2。
如果每次迭代的機率為 1/2，則預期的迭代次數為 2。這可以為 1/2+1/4+1/8… 機率為 1/2 時需要 1 次迭代，機率為 1/4恰好取 2（失敗，成功），機率為 1/8 取正好 3（失敗，失敗，成功）等。
對於 k>2，成功的機率只會增加，並且預期的呼叫次數會更低。
因此，預期的執行時間是 SQROOT + O(log(n)) 的 2 次呼叫。附加元素用於 gcd 和隨機選擇部分（甚至接收輸入並給出輸出）。