べき剰余の求め方（繰り返し二乗法）

べき剰余は、$a^b$ を m で割った余りのことです。素直に考えれば $a^b$ を計算してから m で割ればよいのですが、それでは指数が少し大きくなっただけで手に負えなくなります。既定の入力 $7^{128}$ は 109 桁の数で、ふつうの電卓では表示すらできません。

それでも余りだけなら求められます。次の性質があるからです。

掛けてから余りを取っても、先に余りを取ってから掛けても、答えは同じという意味です。ですから掛けるたびに余りを取ってしまえば、途中の数が m より大きくなることはありません。109 桁の数を持つ必要がなくなります。

128 回掛けずに済ませる

とはいえ 128 回掛けるのは無駄です。二乗を繰り返すと、掛ける回数を一気に減らせます。

• $7^2 = 49$ で、13 で割った余りは 10
• $7^4$ は $7^2$ の二乗なので、$10^2 = 100$ から余りは 9
• $7^8$ は $7^4$ の二乗なので、$9^2 = 81$ から余りは 3
• $7^{16}$ は $3^2 = 9$ で、余りは 9
• $7^{32}$ は $9^2 = 81$ で、余りは 3
• $7^{64}$ は $3^2 = 9$ で、余りは 9
• $7^{128}$ は $9^2 = 81$ で、余りは 3

7 回の二乗で 128 回の掛け算が終わりました。答えは 3 です。

128 は 2 を 7 回掛けた数なので、ちょうど二乗を 7 回繰り返すだけで届きました。指数がそういうきりのいい数でないときは、指数を 2 進法で書いて、1 が立っている桁のぶんだけ掛け合わせます。たとえば $7^{10}$ なら、10 は 2 進法で 1010 ですから、$7^8 \times 7^2$ と組み立てます。掛け算の回数は、多くても指数の 2 進法の桁数の 2 倍で収まります。

使いどころ

この計算は暗号を支えています。RSA 暗号では数百桁の数を大きな指数で累乗する計算を繰り返しますが、そのまま累乗していたら宇宙の年齢をかけても終わりません。繰り返し二乗法なら一瞬で済みます。フェルマーの小定理を確かめるときにも使います。m が素数で、a が m の倍数でなければ、$a^{m-1}$ を m で割った余りは必ず 1 になる、という定理です。

気をつけること

m を 1 にすると、どんな数を割っても余りは 0 になります。$a^0 = 1$ のときも、1 を 1 で割った余りは 0 です。

桁数の欄には、$a^b$ をそのまま書いたときの桁数が出ます。これは $b \times \log_{10} a$ から求めています。答えの余りは m より小さい数なのに、もとの数はこれだけ大きいのだ、という目安として見てください。