Paillier暗号
k を任意の整数とするとき、
( 1 + n ) k = 1 + k n + k ( k − 1 ) 2 n 2 + ⋯ = 1 + k n + n 2 ( k ( k − 1 ) 2 + ⋯ ) = 1 + k n mod n 2 {\displaystyle (1+n)^{k}=1+kn+{\frac {k(k-1)}{2}}n^{2}+\cdots =1+kn+n^{2}\left({\frac {k(k-1)}{2}}+\cdots \right)=1+kn\mod n^{2}}
が成立する。同様の議論で、
( 1 + l n ) k = 1 + k l n mod n 2 {\displaystyle (1+ln)^{k}=1+kln\mod n^{2}}
が成立する事もわかる。
この事実から、次の定理が分かる。
定理2 G は 1 + n を生成元とする位数 n の巡回群である。
証明 G の位数が n であるのはすでに証明済みである。各 k = 0, ..., n − 1 に対し、(1 + kn) = 1 + kn = 1 mod n なので、1 + kn は 1 の n 乗根である。しかも n 個の元 1 + 0n, ..., 1 + (n − 1)n はいずれも相異なる。
Paillier暗号は群 Z n 2 ∗ {\displaystyle \mathbb {Z} _{n^{2}}^{*}} を利用するので、群 Z n 2 ∗ {\displaystyle \mathbb {Z} _{n^{2}}^{*}} の構造を調べる。 Z n 2 ∗ {\displaystyle \mathbb {Z} _{n^{2}}^{*}} の位数 φ(n) は、
φ(n) = n(1 − 1/p)(1 − 1/q) = n(p − 1)(q − 1)
である。(オイラーのφ関数参照。)n と (p − 1)(q − 1) は互いに素なので、 Z n 2 ∗ {\displaystyle \mathbb {Z} _{n^{2}}^{*}} には位数 n の部分群 G と位数 (p − 1)(q − 1) の部分群 H が存在し、 Z n 2 ∗ = G × H {\displaystyle \mathbb {Z} _{n^{2}}^{*}=G\times H} である(アーベル群の基本定理より)。
λ = lcm(p − 1, q − 1) とすると、n と互いに素な任意の a に対し、
a = 1 mod n,
a = 1 mod n
が成立する(カーマイケルの定理)。すなわち、群 Z n ∗ , Z n 2 ∗ {\displaystyle \mathbb {Z} _{n}^{*},\,\mathbb {Z} _{n^{2}}^{*}} の各元の位数はそれぞれ λ, nλ である。