繰り返し二乗法によるべき剰余

指数を 2 進法で表し、 $a^{2^{k}} mod n$ を順に 2 乗して必要なものを掛け合わせることで、 $5^{9} mod 47$ や $22 3^{d} mod 391$ のようなべき剰余を手計算で求められる

前提

合同式（数学A 整数の性質）
n 進法（数学A 整数の性質）

この技能までの道筋（18 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
n 進法（数学A 整数の性質）

説明

$a^{m}$ を $n$ で割った余り（べき剰余）を、 $a$ を $m$ 回掛けることなく求める方法です。指数 $m$ を 2 進法で表し、 $a, a^{2}, a^{4}, a^{8}, \dots$ の余りを「2 乗しては余りを取る」ことで順に作り、必要なものだけを掛け合わせます。指数が数十〜数百あっても、掛け算はおよそ $2 lo g_{2} m$ 回で済みます。RSA 暗号の暗号化・復号や、合同式での大きな累乗の計算などで使います。

なぜそうしてよいのか

指数 $m$ を 2 進法で $m = 2^{k_{1}} + 2^{k_{2}} + \dots + 2^{k_{r}}$ （ $k_{1} > k_{2} > \dots > k_{r} \geq 0$ ）と表すと、指数法則により $a^{m} = a^{2^{k_{1}}} \cdot a^{2^{k_{2}}} \dots a^{2^{k_{r}}}$ となります。つまり $a^{2^{k}}$ という形の数さえ用意できれば、あとは 2 進表示で桁が $1$ のところに対応するものを掛ければよいのです。

その $a^{2^{k}}$ は、 $a^{2^{k + 1}} = a^{2^{k} \cdot 2} = (a^{2^{k}})^{2}$ なので、一つ前のものを 2 乗するだけで次が得られます。しかも合同式は積について閉じている（ $x \equiv x^{'} (mod n), y \equiv y^{'} (mod n)$ なら $x y \equiv x^{'} y^{'} (mod n)$ ）ので、毎回 $n$ で割った余りに置き換えてから 2 乗したり掛けたりしてよく、扱う数はいつも $n^{2}$ 未満に収まります。

たとえば $m = 29$ なら、 $a$ を 28 回掛ける代わりに、2 乗 4 回と掛け算 3 回の計 7 回で済みます。指数が大きいほどこの差は劇的になります。

手順

指数 $m$ を 2 進法で表し、 $m = 2^{k_{1}} + 2^{k_{2}} + \dots$ と 2 のべきの和に分ける。
$a$ を $n$ で割った余り $r_{0}$ から始め、 $r_{k + 1} \equiv r_{k}^{2} (mod n)$ （2 乗して $n$ で割った余り）を繰り返して、 $a^{2^{k}} mod n$ の表を 2 進表示の最上位の桁まで作る。
2 進表示で桁が $1$ の位置 $k$ に対応する $r_{k}$ だけを選び、掛け合わせる。掛けるたびに $n$ で割った余りに置き換える。
最後に得た $0$ 以上 $n - 1$ 以下の数が $a^{m}$ を $n$ で割った余りである。

例題

$3^{29}$ を $47$ で割った余りを求めよ。

例題の解答

【手順 1】 $29 = 16 + 8 + 4 + 1 = 1110 1_{(2)}$ なので $3^{29} = 3^{16} \cdot 3^{8} \cdot 3^{4} \cdot 3^{1}$ 。

【手順 2】2 乗して余りを取ることを繰り返す（法は $47$ ）。
$3^{1} \equiv 3$
$3^{2} \equiv 9$
$3^{4} \equiv 9^{2} = 81 \equiv 81 - 47 = 34$
$3^{8} \equiv 3 4^{2} = 1156 = 47 \cdot 24 + 28 \equiv 28$
$3^{16} \equiv 2 8^{2} = 784 = 47 \cdot 16 + 32 \equiv 32$

【手順 3】桁が $1$ の $3^{16}, 3^{8}, 3^{4}, 3^{1}$ を掛け、そのつど余りを取る。
$32 \cdot 28 = 896 = 47 \cdot 19 + 3 \equiv 3$
$3 \cdot 34 = 102 = 47 \cdot 2 + 8 \equiv 8$
$8 \cdot 3 = 24$

【手順 4】 $24$ は $0$ 以上 $46$ 以下なので、 $3^{29} \equiv 24 (mod 47)$ 。求める余りは $24$ 。

答え: $24$

よくある誤り

選んだ $a^{2^{k}}$ どうしを掛けるときに指数を掛けてしまう誤り（ $3^{16} \cdot 3^{8} = 3^{128}$ など）。正しくは指数は足し算で $3^{16} \cdot 3^{8} = 3^{24}$ 。だから 2 進表示の各桁の値の和が元の指数 $29$ に一致する。
次の段を作るときに 2 乗ではなく 2 倍してしまう誤り（ $3^{4} \equiv 34$ から $3^{8} \equiv 2 \cdot 34 = 68 \equiv 21$ とする）。正しくは $3^{8} = (3^{4})^{2} \equiv 3 4^{2} \equiv 28 (mod 47)$ 。
指数まで $n$ で割った余りに置き換えてしまう誤り（ $2^{50} \equiv 2^{50 - 47} = 2^{3} = 8 (mod 47)$ とする）。合同式で置き換えてよいのは底と途中の値だけで、指数は置き換えられない。正しく計算すると $2^{50} \equiv 16 (mod 47)$ 。
2 進表示を間違える、または桁が $0$ の位置の値まで掛けてしまう誤り（ $29$ を $16 + 8 + 4 + 2 + 1$ として $3^{31}$ を計算するなど）。掛ける前に、選んだ 2 のべきの和が指数に一致するか（ $16 + 8 + 4 + 1 = 29$ ）を必ず確かめる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

RSA 暗号の鍵生成・暗号化・復号（大学数学暗号理論）
ディフィー・ヘルマン鍵共有（大学数学暗号理論）
ベビーステップ・ジャイアントステップ法（大学数学暗号理論）
ポーリッヒ・ヘルマン法による離散対数（大学数学暗号理論）
べきの塔の剰余（大学院数学計算理論・ラムダ計算）
平方剰余とオイラーの規準（大学数学整数論）