補題(CS)の証明 - 暗号理論教室

補題(CS)の証明

証明
ユークリッドの互除法を用いて、以下の b', k を計算:

• b b' = 1 + a k.

x'を

• x' = x^b' y^-k (mod N)

とおけばよい。

• • x'^a ≡ x^b'a y^-ka ≡ y^bb' y^-ka ≡ y (mod N).

Q.E.D.

---