利用者:Meauk/sandbox

成立の証拠

値 d の正体

a が {(g^{p - 1} mod p²) - 1} / p に等しいということは、g^{p - 1} mod p² が ap + 1 に等しいことを意味する。これには次の2点が関わる。

1. フェルマーの小定理によれば g^{p - 1} ≡ 1 (mod p) が成立するということ。
2. 任意の正整数 x を考える時、x mod p² において p² を含む全ての項は 0 になるので、その結果は「p¹ の項」よりも大きいことはないということ。

したがって、a とは「g^{p - 1} を p² で割った時の p¹ の項の係数」であると述べることができる。

その上で、d が ad ≡ 1 (mod p) によって求められるというので、この d は「法 p における a の逆元」に相当することになる。

暗号文 C の正体

暗号文は C ≡ g^{m + nr} (mod n²) によって求められるが、これは言い換えると C ≡ g^m × g^pqr (mod p²q²) である。

値 D の正体

第一に C^{p - 1} mod p² について考える。