為什麼要開平方(modn)(modn)pmod n尋找ppp和qqq（作為n=p⋅qn=p⋅qn = p cdot q)?
讓 $ n = p*q $ ， 和 $ p \neq q $ 和 $ x^2=1 \pmod n $ , $ x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n $ （所以 x 是一個非平凡的平方根 mod n。）
我不明白如何 $ \gcd(x+1,n) \in {p,q} $ 跟隨。
我明白那個 $ x^2=(x+1)(x-1) $ ， 所以 $ n=p*q $ 是一個因素 $ (x+1)(x-1) $ , 但兩者都不是 $ (x+1) $ 也不是 $ (x-1) $ （因為 ax 是一個重要的解決方案）。到目前為止，我所看到的每一個證據都在這一點上停止，讓我感到困惑。在我看來，它認為 $ gcd(x+1,n) \in {1,p,q} $ （所以簡單的解決方案 1 確實是可能的）。我們如何確定 $ x+1 $ 和 n 有不是 1 的公因數？我確定我遺漏了一些非常明顯的東西，但我無法弄清楚。
如果 $ x^2\equiv1\mod{n} $ ， 代表著 $ (x+1)(x-1)\equiv0\mod n $ . 換句話說， $ (x+1)(x-1)=k\cdot n=k\cdot p\cdot q $ 對於一些 $ k\in\mathbb{N} $ . 你去了：如果 $ x\neq\pm 1\mod n $ ， 兩者都不 $ x+1 $ 也不 $ x-1 $ 等於 $ p\cdot q $ 並且必須在它們的因式分解中包含任何一個素數（可能加上一些因子 $ k $ ）。因此， $ \gcd(x+1,n)\in{p,q} $ .
你有
$ x^2 \equiv 1 \pmod n $ 和 $ x \neq \pm 1 \pmod n $
現在我們可以寫 $ x^2 -1 = 0 + n\cdot k $ 對於一些 $ k \in \mathbb{Z} $ .
那是 $ (x-1)(x+1) = n \cdot k $ .
- 所以如果你拿 $ \gcd(x+1, n) $ 和 $ \gcd(x-1,n) $ 那麼其中一個必須大於 1。否則我們必須 $ (x-1)(x+1) = k $ 自平等以來失敗。
- 另外，如果我們現在 $ n = p \cdot q $ 我們可以看看 $ (x-1)(x+1) = n \cdot k $ 作為;$$ (x-1)(x+1) = p \cdot q \cdot k $$意思就是 $ p $ 和 $ q $ 必須分開 $ (x-1) $ 或者 $ (x+1) $ 這將使 GCD 不同於 1。