拉賓密碼系統 - 有多少解決方案？
如果在拉賓密碼系統中我們有 $ n = p \cdot q $ 在哪裡 $ p $ 和 $ q $ 是素數我們有四個解（根） - 存在四個解 $ x^2 \equiv b \pmod{n} $ .
但是，當我們有：
$ n = p \cdot q \cdot r $
在哪裡 $ p $ 和 $ q $ 和 $ r $ 是素數或：
$ n = p \cdot q \cdot r \cdot z $
在哪裡 $ p $ 和 $ q $ 和 $ r $ 和 $ z $ 是素數
我們會有多少解決方案？
他們會 $ 2^k $ ? 在哪裡 $ k $ 是素數的個數？
我們會有多少解決方案？
假設：
- $ p, q, r, …, z $ 是不同的奇數素數
- $ b $ 相對質數 $ n $
- 存在至少一種解決方案
那麼，是的，將會有 $ 2^k $ 解決方案。
這是直截了當的展示；我們知道有一個解決方案 $ x_0 $ 這樣 $ x_0^2 = b \pmod n $ , 那麼這意味著：
$$ x_0^2 = b \pmod p $$ $$ x_0^2 = b \pmod q $$ …
$$ x_0^2 = b \pmod z $$ 我們知道第一個方程有兩個模解 $ p $ ; $ x_0 $ 和 $ -x_0 $ （作為 $ b $ 相對質數 $ p $ ， 因此 $ x_0 \ne 0 \pmod p $ ， 和 $ p $ 很奇怪，所以 $ x_0 \ne -x_0 \pmod p $ ）。我們也知道不可能有第三個（因為這意味著對 $ p $ , 與以下假設相矛盾 $ p $ 是素數）。
同樣，其餘方程有 2 個解；因此使用中國剩餘定理，有 $ 2^k $ 是將這些解決方案重新組合成一個 $ x $ 滿足所有這些方程的值（因此是原始方程）。
我們還可以證明任何值 $ x $ 不在集合中 $ 2^k $ 將不滿足主要等價之一，因此不能滿足原始等價，因此我們精確地 $ 2^k $ 解決方案。