計算根模是複合的嗎ññN一個不知道分解的難題ññN?
假設我們得到 $ \mathbb{Z}{N} $ 和一個元素 $ x^u \in \mathbb{Z}{N} $ 和 $ u \in (0,l] $ 在哪裡 $ l $ 是位大小 $ N $ . 是不是很難恢復 $ x $ 通過知道 $ u $ 在不知道因式分解的情況下 $ N $ ?
是的，尋找未知隨機數的問題 $ x\in\mathbb Z_N $ 給定 $ N\in\mathbb N $ , $ u\in\mathbb N $ 和 $ 1<u\le\lceil\log_2N\rceil $ ， 和 $ x^u $ 計算在 $ \mathbb Z_N $ , 除非分解 $ N $ 可以確定，對於適當構造的 RSA 模數，這本身被認為是困難的 $ N $ . 此外，根據 $ u $ 和 $ N $ ，可能有幾種解決方案無法分辨出正確的解決方案（如果 $ u $ 是奇怪的並且 $ N $ squarefree無除數 $ \lceil\log_2N\rceil $ 那麼有一個單一的解決方案）。請注意，我已排除 $ u=1 $ （問題允許），因為它可以找到 $ x $ 瑣碎的。
什麼時候 $ u $ 奇怪的是，這是具有小指數的 RSA 問題，當分解 $ N $ 無法確定（需要注意的是，該問題的通常定義要求 $ N $ 是無平方且沒有小除數的）。
什麼時候 $ u $ 是 $ 2 $ ，這是平方根模未知複合問題，當分解 $ N $ 無法確定。
能夠始終如一地解決平方根問題和 RSA 問題意味著能夠通過編寫來找到問題問題的解決方案 $ u $ 作為 $ e\cdot2^s $ 奇怪的 $ e $ , 求解指數的 RSA 問題 $ e $ ，並解決平方根問題 $ s $ 次。
另外：此答案適用於問題的第 5 版。正如該問題早期版本的另一個答案中正確指出的那樣，知道 $ N $ 是一個正方形不會使問題更容易，如果分解 $ N $ 仍然未知。
進一步補充以下評論：
- 很容易找到任何給定元素的逆 $ \mathbb Z_N $ 當它存在時，使用擴展歐幾里得算法。
- 很難展示 $ a\in\mathbb Z_N $ 沒有反模 $ N $ ， 以外 $ 0 $ 或一個容易找到的因子的倍數 $ N $ （論證：如果這樣一個 $ a $ 被發現了，然後 $ \gcd(a,N) $ 將是一個非平凡的除數 $ N $ 有助於找到完整的因式分解 $ N $ ).
- 如果 $ \gcd(u,N)=1 $ （我們將在下文中假設），因此很容易找到非負整數 $ v $ 和 $ k $ 和 $ u\cdot v=k\cdot N+1 $ , 否則用 $ v\equiv u^{-1}\pmod N $ .
- 它確實遵循 $ \forall x\in\mathbb Z_N $ , $ (x^u)^v=x^{k\cdot N+1}=(x^N)^k\cdot x $ .
- 這似乎無助於尋找 $ x $ ，因為我們沒有什麼告訴我們 $ x^N=1 $ ; 相反， $ x^N=1 $ 很少舉行 $ x\ne 1 $ ; 尤其 $ x^N=1 $ 僅適用於 $ x=1 $ 什麼時候 $ N $ 是素數，因為在這種情況下： $ \forall x\in\mathbb Z_N $ , $ x^N=x $ 由費馬小定理。