G の構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/08/07 01:23 UTC 版)
「Paillier暗号」の記事における「G の構造」の解説
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}} が成立する事もわかる。 この事実から、次の定理が分かる。 定理2G は 1 + n を生成元とする位数 n の巡回群である。 証明G の位数が n であるのはすでに証明済みである。各 k = 0, ..., n − 1 に対し、(1 + kn)n = 1 + kn2 = 1 mod n2 なので、1 + kn は 1 の n 乗根である。しかも n 個の元 1 + 0n, ..., 1 + (n − 1)n はいずれも相異なる。G の元の個数は n だったので、以上の議論より、G = {1 + kn | k = 0, ..., n − 1} である。しかも (1 + n)k = (1 + kn) mod n2 なので、1 + n は G の生成元である。 各 k = 0, ..., n − 1 に対し、(1 + kn)n = 1 + kn2 = 1 mod n2 なので、1 + kn は 1 の n 乗根である。しかも n 個の元 1 + 0n, ..., 1 + (n − 1)n はいずれも相異なる。したがって G = {1 + kn | k = 0, ..., n − 1} である。しかも (1 + n)k = (1 + kn) mod n2 なので、1 + n は G の生成元である。 G の任意の元 g はある k ∈ {0, ..., n − 1} を用いて g = 1 + kn mod n2 と表現できる。そこで関数 L: G → Zn を L : u ↦ ( u − 1 ) / n {\displaystyle L\colon u\mapsto (u-1)/n} により定義すると、L(g) = k であり、L が乗法群 G から加法群 Zn への同型写像である事が分かる。
※この「G の構造」の解説は、「Paillier暗号」の解説の一部です。
「G の構造」を含む「Paillier暗号」の記事については、「Paillier暗号」の概要を参照ください。
- G の構造のページへのリンク
