Factoring
平方根，素數分解
我被困在我的作業中，因為它的作業，我寧願得到一些提示而不是完整的解決方案。問題出在：
如果您知道 51733469 (mod 88416763) 的平方根是 50224876、38191887、22222、88394541，則因式分解 n = 88416763。
按照 CodesInChaos 將提示轉換為完整解決方案的請求，這裡有一個完整的解決方案。讓 $ x $ 和 $ y $ 是平方根 $ 51733469 $ 模組 $ n $ . 它遵循
$$ 0\equiv x^2-y^2=(x+y)(x-y),(\textrm{mod }n). $$ 如果我們選擇 $ x\not\equiv \pm y, (\textrm{mod }n) $ ， 然後 $ x-y $ 和 $ x+y $ 不能被 $ n $ . 另一方面， $ n\mid (x+y)(x-y) $ ， 所以 $ \gcd(x+y,n)\neq 1\neq \gcd(x-y,n) $ . 選擇例如 $ x = 38191887 $ 和 $ y=22222 $ 給
$$ \gcd(x-y,n) = 8887,;; \gcd(x+y,n)=9949. $$ 直接計算表明 $ n=88416763 = 8887\times 9949 $ . 使用埃拉托色尼篩法很容易計算出所有小於 $ 100 $ 然後檢查它們中的任何一個是否除任一因子，這將表明 $ 8887 $ 和 $ 9949 $ 都是素數。