butch’s blog

メモ置き場。

【5.1公開鍵暗号】暗号文から元のメッセージを復元する時の計算

量子コンピュータ

「量子コンピュータ入門(古澤明著)」の5.1章で暗号文から元のメッセージを復元する時の途中計算(p71)のメモになります。

https://www.amazon.co.jp/量子コンピュータ入門-第2版-宮野-健次郎/dp/4535788057

以下の途中計算になります。

\begin{align} C^d \; \text{mod}\;M &= (P^e)^d \; \text{mod}\;M \tag{1}\\ &= P^{ed} \; \text{mod}\;M \tag{2} \\ &= P^{k(p-1)(q-1) + 1} \; \text{mod}\;M \tag{3} \\ &= P \cdot P^{k(p-1)(q-1)} \;\text{mod}\;M(=pq) \tag{4} \\ &= P \;\text{mod}\;M \tag{5} \end{align}

数式の番号は適当に降りました。
問題となるのが(4)から(5)の式変形だと思います。
本の中ではフェルマーの小定理を使うように指示されています。
ただこの形のままではそのまま使うことが出来ません。

フェルマーの小定理とは

  • pが素数でgとpが互いに素の場合、$g^{p-1} \equiv 1\;(\text{mod}\;p)$が成り立つ。

(4)から(5)では$P^{k(p-1)(q-1)} = nM + 1$(nは整数)が成り立てばいいことが分かります。
$p, q$それぞれ単独で見ていきましょう。
まずは$p$だけに注目すると$P, p$は互いに素なので、

\begin{align} P^{p-1} \equiv 1 \;(\text{mod}\; p) \end{align}

さらに両辺を$k(q-1)$乗すると、

\begin{align} P^{k(p-1)(q-1)} \equiv 1 \;(\text{mod}\; p) \end{align}

よって、$P^{k(p-1)(q-1)} = xp + 1$($x$は整数)と表すことが出来ます。
$q$についても同様にして、$P^{k(p-1)(q-1)} = yq + 1$($y$は整数)と表せます。
これらが等しいので$xp = yq$となります。
ここで$p, q$が互いに素なので$x=qz, y=pz$となる整数$z$が存在します。
以上より$P^{k(p-1)(q-1)} = zpq + 1$と表せることが出来ました。
これを利用すると(4)から(5)の式変形が可能になります。