利用者: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 の逆元」に相当することになる。

値 D の正体

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

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

この時、次の2点に注意する。

1. 任意の正整数 x₂ を用いて (x₂ mod p²q²) mod p² を計算することを考える時、それは初めから x₂ mod p² を計算することと同じである。
2. p² に対応するカーマイケル数は p(p - 1) であるから、任意の正整数 x₃ を考えると x₃^{p(p - 1)} mod p² の結果は常に 1 となる。