因數大ññN給定oracle以求平方根模ññN
什麼時候 $ p $ 和 $ q $ 是不同的奇數素數和 $ N = pq $ , 中的點 $ \mathbb Z_N^\ast $ 有零或四個平方根。四分之一的點有四個平方根；其餘的沒有平方根。的四個平方根 $ x\in\mathbb Z_N^\ast $ 看起來像 $ \pm a $ , $ \pm b $ . （當然， $ -a $ 方法 $ N-a $ 因為我們正在模數工作 $ N $ .) 假設我給你一個有效的確定性算法 $ S $ 那，在輸入 $ x $ 有平方根，找到一些平方根 $ x $ . （如果 $ x $ 沒有平方根，它返回 $ \bot $ .)
利用 $ S $ 制定有效的機率算法 $ F $ 那個因素 $ N $ .
$$ Hint: If you can find two square roots of a number, call them $a$ and $b$, which are not of the form $a \equiv \pm b \pmod N$, then you can factor $N$. Show how. $$注意：你只能打電話 $ S $ 作為一個黑盒，所以你不知道它會找到哪個平方根。
我無法理解這個作業問題，有人可以指導我或提示如何進行嗎？到目前為止我想出的是，第一次呼叫算法 $ S $ 在某個數字上找到平方根 $ a $ . 反複呼叫它直到我得到 $ b $ 這不是形式 $ a \equiv \pm b \pmod N $ . 對所有點重複此操作。我仍然堅持如何使用它來考慮因素 $ N $ 儘管。
到目前為止我想出的是，第一次呼叫算法 $ S $ 在某個數字上找到平方根 $ a $ . 反複呼叫它直到我得到 $ b $ 這不是形式 $ a\equiv\pm b\pmod N $ . 對所有點重複此操作。
這有（至少）兩個問題：
- 對於固定輸入， $ S $ 將始終返回相同的平方根。
- 您不能“對所有點重複此操作”，因為有 $ \mathcal O(N) $ 其中，因此你的算法 $ F $ 不會是（機率）多項式時間。
至於我們如何解決這個問題：因為 $ S $ 只會給我們一個平方根，我們必須以某種方式自己獲得另一個（模否定）。一個好的（有效的）方法是簡單地構造給定的數字 $ S $ 以一種我們已經知道它的平方根的方式，並希望 $ S $ 會給我們另一個。這是一個算法：
- 選擇 $ x\in\mathbb Z_N^\ast $ 隨機。
- 通過它的廣場 $ x^2 $ 至 $ S $ ; 呼叫結果 $ y $ .
- 如果 $ x\equiv\pm y\pmod N $ ，我們很不幸：從一個新的開始 $ x $ .
- 至此，我們從 $$ x^2\equiv y^2\pmod N $$ 那 $$ x^2-y^2=(x+y)(x-y) $$ 是非零倍數 $ N $ 雖然兩者都沒有 $ x+y $ 也不 $ x-y $ 僅是，因此我們可以恢復一個因子 $ N $ 通過計算 $$ \gcd(x+y,N) \text. $$
現在我們想證明這個算法（機率上）是有效的。我們的選擇 $ x $ 相當於先選了一些正方形 $ r $ 隨機然後選擇 $ x $ 作為其中之一 $ r $ 的平方根也是隨機的。神諭 $ S $ 是確定性的，因此將始終返回相同的平方根 $ y $ 的 $ r $ . 因此我們有機率 $ \frac12 $ 我們的選擇 $ x $ 不在同一個“類”中 $ y $ ， IE $ x\not\equiv\pm y\pmod N $ ，從而產生分解。顯然，該算法的一次迭代在多項式時間內執行，預期成功的迭代次數僅為 $ 1+\frac12+\frac14+\dots=2 $ . 所以 $ F $ 有效因素 $ N $ .