こんにちは！
今回は、大きな数字の累乗を計算する方法です！
えっ！？暗号の解説じゃないのかって？
その通り、この解説は暗号化の解説なのですが、暗号化を解説するために「大きな数字の累乗」の計算が必要となったのです。
最終目的地は「公開鍵暗号」の解説ですので、忘れないでくださいね。
「\(x \pmod n\)」は「\(x\)を\(n\)で割り算した余り」という意味です。
もし、\(x\)を\(n\)で割ったときの「商」を\(K\)とし、「余り」を\(A\)とすれば、「\(x = Kn + A\)」となりますね。
(例えば、13を5で割ると、商は「2」、余りは「3」になります。だから、「\(13 = 5 \times 2 +3\)」と書くことができます)
さて、ここで突然ですが、\(x\)と\(y\)という2つの数字があったとしましょう。
それぞれ、\(n\)で割ったときの商は「\(K_x\)」と「\(K_y\)」と置きます。
さらに、\(n\)で割ったときの余りは「\(A_x\)」と「\(A_y\)」と置きます。
このとき、\(x \times y\)を\(n\)で割ったときの余りはどうなるでしょうか？
先ほどみたように、「\(x=K_xn+A_x\)」と書けますし、「\(y=K_yn+A_y\)」と書けます。
なので、\(x \times y=(K_xn+A_x)(K_yn+A_y)=K_xK_yn^2+K_xnA_y+K_ynA_x+A_xA_y\)となります。
つまり、\(x \times y\)を\(n\)で割るとどうなるかというと、\(K_xK_yn^2\)も、\(K_xnA_y\)も、\(K_ynA_x\)も、全部\(n\)で割り切れるので、余りが出ません。
唯一、余りがでるのは\(A_xA_y\)の部分です。
つまり、\(x \times y\)を\(n\)で割ったとの余りは、\(x\)を\(n\)で割ったとの余り(\(A_x\))と\(y\)を\(n\)で割ったとの余り(\(A_y\))を掛け算したものを\(n\)で割ったときの余りと同じになります。
このことを数式で書くと「\(x \times y = A_x \times A_y \pmod n\)」となりますね。
で・・・。このことが何の役にたつの？
でも、どうせ掛け算した結果を\(n\)で割り算した余りを求めるのであれば、はじめから\(x\)を\(n\)で割り算した結果と、\(y\)を\(n\)で割り算した結果を掛け算して、その結果をもう一度\(n\)で割り算すればいいですよね。
\(x\)や\(y\)が大きくても、それを\(n\)で割った数は必ず\(n\)以下になるので、小さい数字になって計算が楽になるはずです。
この応用編ですが、例えば「\(x^{100} \pmod n\)」を計算しなければいけないのであれば、「\(x^{100}=(x^{10})^{10}\)」という事実を使います。
(「\(x^{100}\)」というのは、\(x\)を100回掛け算したものでした。「\((x^{10})^{10}\)」は、\(x\)を10回掛け算したもの(\(x \times x \times x \times x \times x \times x \times x \times x \times x \times x\))を、さらに10回掛け算しなさいということなので、結局「\(x\)を100回掛け算する」ということと同じなんです。)
「\(x^{100}=(x^{10})^{10} = x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10}\)」なので、「\(x^{100} \pmod n\)」は「\(x^{10} \pmod n\)」を計算した後に、それを10回掛け算して、もう一度\(n\)で割り算した余りを求めればいいんです。
「\(x^{10}\)」ならば「\(x^{100}\)」の計算よりも簡単です。(「\(x^{10}\)」の計算すら難しければ、もっと小さくして「\(x^{5}\)」とかにすればいいだけです)
こうやって、累乗を分割することで、大きな数の累乗の計算もできるようになります。
もうこれで、大きな数も怖くないですね。
次回は、今回解説した方法を活用して「\(7846^{13709}\)」の計算をしましょう！
果たして、元のメッセージ「16」が出てくるでしょうか？
今回は、大きな数字の累乗を計算する方法です！
えっ！？暗号の解説じゃないのかって？
その通り、この解説は暗号化の解説なのですが、暗号化を解説するために「大きな数字の累乗」の計算が必要となったのです。
最終目的地は「公開鍵暗号」の解説ですので、忘れないでくださいね。
\(n\)で割り算した「余り」を計算するとき、次の関係を使うと掛け算の計算が楽になるよ。
- 「\(A \times B\)を\(n\)で割った余り」\(=\)「\(A\)を\(n\)で割った余り」\(\times\)「\(B\)を\(n\)で割った余り」を\(n\)で割った余り
- 「\(x^{100}\)を\(n\)で割った余り」\(=\)「\(x^{10}\)を\(n\)で割った余り」を\(10\)乗したものを\(n\)で割った余り
大きな数の累乗の余りを計算する方法・・の巻！
「大きな数の累乗」の計算方法の前に、「\(x \pmod n\)」について真剣に考えてみましょう。「\(x \pmod n\)」は「\(x\)を\(n\)で割り算した余り」という意味です。
もし、\(x\)を\(n\)で割ったときの「商」を\(K\)とし、「余り」を\(A\)とすれば、「\(x = Kn + A\)」となりますね。
(例えば、13を5で割ると、商は「2」、余りは「3」になります。だから、「\(13 = 5 \times 2 +3\)」と書くことができます)
さて、ここで突然ですが、\(x\)と\(y\)という2つの数字があったとしましょう。
それぞれ、\(n\)で割ったときの商は「\(K_x\)」と「\(K_y\)」と置きます。
さらに、\(n\)で割ったときの余りは「\(A_x\)」と「\(A_y\)」と置きます。
このとき、\(x \times y\)を\(n\)で割ったときの余りはどうなるでしょうか？
先ほどみたように、「\(x=K_xn+A_x\)」と書けますし、「\(y=K_yn+A_y\)」と書けます。
なので、\(x \times y=(K_xn+A_x)(K_yn+A_y)=K_xK_yn^2+K_xnA_y+K_ynA_x+A_xA_y\)となります。
つまり、\(x \times y\)を\(n\)で割るとどうなるかというと、\(K_xK_yn^2\)も、\(K_xnA_y\)も、\(K_ynA_x\)も、全部\(n\)で割り切れるので、余りが出ません。
唯一、余りがでるのは\(A_xA_y\)の部分です。
つまり、\(x \times y\)を\(n\)で割ったとの余りは、\(x\)を\(n\)で割ったとの余り(\(A_x\))と\(y\)を\(n\)で割ったとの余り(\(A_y\))を掛け算したものを\(n\)で割ったときの余りと同じになります。
このことを数式で書くと「\(x \times y = A_x \times A_y \pmod n\)」となりますね。
で・・・。このことが何の役にたつの？
大きな数の累乗に、「\(x \times y = A_x \times A_y \pmod n\)」を使う
もし、\(x\)や\(y\)がとっても大きな数字だと、その掛け算をするのも大変です。でも、どうせ掛け算した結果を\(n\)で割り算した余りを求めるのであれば、はじめから\(x\)を\(n\)で割り算した結果と、\(y\)を\(n\)で割り算した結果を掛け算して、その結果をもう一度\(n\)で割り算すればいいですよね。
\(x\)や\(y\)が大きくても、それを\(n\)で割った数は必ず\(n\)以下になるので、小さい数字になって計算が楽になるはずです。
この応用編ですが、例えば「\(x^{100} \pmod n\)」を計算しなければいけないのであれば、「\(x^{100}=(x^{10})^{10}\)」という事実を使います。
(「\(x^{100}\)」というのは、\(x\)を100回掛け算したものでした。「\((x^{10})^{10}\)」は、\(x\)を10回掛け算したもの(\(x \times x \times x \times x \times x \times x \times x \times x \times x \times x\))を、さらに10回掛け算しなさいということなので、結局「\(x\)を100回掛け算する」ということと同じなんです。)
「\(x^{100}=(x^{10})^{10} = x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10} \times x^{10}\)」なので、「\(x^{100} \pmod n\)」は「\(x^{10} \pmod n\)」を計算した後に、それを10回掛け算して、もう一度\(n\)で割り算した余りを求めればいいんです。
「\(x^{10}\)」ならば「\(x^{100}\)」の計算よりも簡単です。(「\(x^{10}\)」の計算すら難しければ、もっと小さくして「\(x^{5}\)」とかにすればいいだけです)
こうやって、累乗を分割することで、大きな数の累乗の計算もできるようになります。
もうこれで、大きな数も怖くないですね。
次回のお知らせ
今回は「大きな数を累乗」する方法を解説しましたが、もともとやりたかったことは、「\(7846^{13709}\)」の計算です。次回は、今回解説した方法を活用して「\(7846^{13709}\)」の計算をしましょう！
果たして、元のメッセージ「16」が出てくるでしょうか？