Paillier 論文：數論引理似乎不起作用
我正在閱讀原始的 Paillier 論文。
我已經達到引理 3：如果 $ g $ 是非零倍數 $ n $ ， 然後 $ \varepsilon_g(x,y) = g^x y^n \mod n^2 $ 是一個雙射，其中 $ x \in \mathbb{Z}_n $ 和 $ y \in \mathbb{Z}_n^* $ .
舉個例子 $ n=6 $ , $ n^2=36, \mathbb{Z}_6^* = {1, 5} $ .
讓 $ g=5 $ . 的順序 $ 5 $ 模組 $ 36 $ 是 $ 6 $ （參見WolframAlpha），它是 $ 6 $ ， 所以 $ \varepsilon_g $ 應該是雙射。
讓 $ (x_1, y_1) = (1, 1) $ 和 $ (x_2, y_2) = (1, 5) $ . 然後：
- $ y_1, y_2 \in \mathbb{Z}_6^* $ 按要求。
- $ \varepsilon(x_1, y_1) = 5^1 \cdot 1^6 = 5 $
- $ \varepsilon(x_2, y_2) = 5^1 \cdot 5^6 = 5 $ （假設運算是模 $ 36 $ .)
所以…這不是雙射。我錯過了什麼嗎？
簡短的回答：這似乎是論文中的一個錯誤，但在實踐中這不是問題。
引理 3 的證明使用以下含義：
自從 $ \gcd(\lambda,n)=1 $ , $ x_2-x_1 $ 一定是的倍數 $ n $ . 最後， $ x_2-x_1=0\bmod n $ 和 $ (y_2/y_1)^n=1\bmod n^2 $ ，這導致唯一的解決方案 $ y_2/y_1=1 $ 超過 $ \mathbb Z_n^\ast $ .
如您的範例所示，斷言 $ \gcd(\lambda,n)=1 $ 一般是錯誤的： $ n=2\cdot 3 $ ， 因此 $ \lambda=(2-1)\cdot(3-1)=2 $ ， 和 $ \gcd(\lambda,n)=2\neq1 $ . 從結構上看，這體現在環 $ \mathbb Z/n^2 $ 包含非平凡的 $ n $ 統一的根——在你的情況下是元素 $ 5 $ ——這使唯一性聲明無效。
不難證明對於 $ n=pq $ 兩個素數的乘積，這種現象發生當且僅當 $ p=2 $ 或者 $ q=2kp+1 $ 對於一些 $ k\in\mathbb N $ . （模重排序的 $ p $ 和 $ q $ .) 對於任何實際大小且隨機生成的素數對，這種情況發生的可能性可以忽略不計 $ (p,q) $ ，因此這在實踐中不會成為問題。