【至急】お願いします。合同式に関して

質問

中学二年なんですが、合同式に関して質問があります。

41の2006乗を43で割った余りは? という問題なのですが、解答を見ますと、

フェルマーの小定理より、
　41の42乗≡1 (mod43)
∴41の2006乗≡(41の42乗)の47乗×41の32乗
　　　　　　≡-2の32乗
　　　　　　≡2の32乗 (mod43)　

ここまではわかります。ただその後の、

ここで、2の8乗≡16の2乗≡-2 (mod43) より、
　41の2006乗≡-2の4乗≡16 (mod43)
よって求める余りは16

までがわからないのです。
特に、「2の8乗≡16の2乗≡-2 (mod43) より、」というのがまったくわからないのです。
私の数学の先生はどうも天才肌のようで、私が聞いてもよくわからないのです。
どなたかわかりやすく説明していただけますでしょうか。至急でお願いします。

回答No.2

Tacosan · ベストアンサー

a^n の計算というのは重要な手順の 1つであり, 効率的に計算する方法についていろんな研究が行われています. 単純な方法として「a からはじめて『直前のものに a を掛ける』, 『直前のものを 2乗する』という処理を繰り返して計算する」というものがあって, 「繰り返し 2乗法」とか呼ばれたりします. この方法では, たとえば a^41 だと (41 を 2進数で書くと 101001 なので) 2乗する→2乗する→a を掛ける→2乗する→2乗する→2乗する→a を掛ける という順に計算していきます. 2進数で「0」の桁では 2乗するだけ, 「1」の桁では 2乗して a を掛けています.
これは p で割った余りを求めるときにも同じように使うことができます. ただし, 2乗したり a を掛けたりしたときには必ず p で割って余りを出し, その次ではこの余りを使うようにします. このようにしても実際に正しい余りが計算でき, しかも途中に出てくる数値は p^2 より小さいので「まじめに a^n を計算して p で割る」より速くなります.
この方法を 2^32 に適用するわけですが, 実は「たまたま」32 = 2^5 なので「直前のものを 2乗する」という計算を 5回繰り返すと計算ができます. 計算結果をちゃんと書くと
2→4→16→256 ≡ -2→4→16
となって, 最終的な余りは 16 だということがわかります. この計算のうち 2^8 = 256 までは 43 で割る必要がないので省略しちゃったんじゃないかなぁ.
ちなみにですが, このように「a^n を p で割った余りを求める」という計算は, いくつかの現代的な暗号で基本的な処理として用いられています.

回答No.1

Tacosan

いや, がんばって 2^32 を計算してもいいんですけど, それはさすがに面倒ですよね? 最終的にほしいのは余りだけなので, もっと簡単に計算しようってことです.
ただ, この場合に関していえば「2乗して 43 で割った余りを求める」ことを 5回繰り返せばいい (2^5 = 32 だから) ので, ちょっと途中を省略しちゃってるのかなぁという感じがします.

お礼

早速ありがとうございます。
つまりこの場合は、偶然「2の8乗≡16の2乗≡-2 (mod43) 」となるので、この方法になるというだけなんでしょうか?
それにしてもどうしてこういう発想になるのでしょうか?　
もう少し細かいところまで教えていただけると、本当にありがたいです。