Number-Theory
可以檢查是否a∈問_n一種∈問Rna in mathrm{QR}_n?
可以檢查 $ a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p) $ 如果 $ p $ 是一個素數。
$ n $ 是一個大的 RSA 模數。是否也可以檢查是否 $ a \in \mathrm{QR}_n $ 如果分解 $ n $ 未知？
可以檢查 $ a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p) $ 如果 $ p $ 是一個素數。
是的，你已經寫下了支票，這就是所謂的歐拉準則。
$ n $ 是一個大的 RSA 模數。是否也可以檢查是否 $ a \in \mathrm{QR}_n $ 如果分解 $ n $ 未知？
如果分解未知，您可以使用Jacobi 符號來確定是否 $ a\in \mathrm{QNR}_n $ , 即，如果 Jacobi 符號是 $ -1 $ .
但是如果 Jacobi 符號產生 $ +1 $ ，那麼你可以有一個二次殘差或一個偽平方，即一個二次非殘差產生雅可比符號 $ +1 $ .
如果因式分解未知，則將偽平方與以 RSA 模為模的二次殘差區分開來稱為二次殘差問題，該問題被認為是一個難題，並且是某些密碼構造（例如Goldwasser-Micali 加密方案）的基礎。
對於通用算法，這個問題可以被證明等價於因式分解。