Prime-Numbers
如果平方模素數，拉賓函式會失去其單向屬性嗎？
我正在研究各種單向函式，我偶然發現了一個 Rabin 函式，它對 RSA 模數取模 $ N=pq $ ， 在哪裡 $ p,q $ 是素數： $ R_N(x) = x^2 \mod N $ .
如果它會失去單向屬性 $ N $ 是素數而不是兩個素數的乘積？
UPD：另外，如果因式分解，拉賓函式是否仍然是單向的 $ N=pq $ 知道嗎？
將 [ $ f_N(x)=x^2\bmod N $ ] 失去單向性質如果 $ N $ 是素數而不是兩個素數的乘積？
是的，多虧了Tonelli-Shanks 算法（這裡的特殊情況）。
$$ Is $$如果因式分解 Rabin 函式仍然是單向的 $ N=pq $ 知道嗎？
不，因為私鑰持有人在拉賓密碼系統中相對於公鑰持有人的主要（“唯一”）資訊優勢是因式分解 $ N $ . 如果即使在已知因式分解下仍保留單向性，則係統將不允許以其正常形式進行解密。
在這種情況下看因式分解如何允許平方根的方法是記住中國剩餘定理在 $ \mathbb Z_N $ 和 $ \mathbb Z_p \times \mathbb Z_q $ …並且如上所述，我們知道如何計算平方根 $ \mathbb Z_p $ .