時計の算術 — mod の世界のべき乗と周期

11時の2時間後は1時。時計は12で「一周」して0に戻ります。このあまりの世界（mod）で足し算・べき乗をすると、暗号の心臓部にある「進むのは一瞬、戻すのは絶望的」という片道の計算が姿を現します。時計盤の上で動かして体感しましょう。

1. 時計の上では数がぐるっと回る — 合同算術

ふつうの数直線はどこまでも伸びますが、時計の数字は 12 まで来ると 0 に戻ります。「13時」を「1時」と言うのは、13 を 12 で割ったあまり（13 mod 12 = 1）を見ているのと同じ。この、法（modulus）n で割ったあまりだけを扱う世界を合同算術（モジュラー算術）と呼びます。足し算は時計の針を進めるのと同じで、n を超えたぶんはぐるっと回り込みます。

下のデモで、足す数 b を n より大きくしてみてください。針が時計を何周もして、最後に残る「あまり」だけが答えになります。

時計の足し算 — n を超えたら回り込む

法 n（目盛りの数）

スタート a

足す数 b

緑＝スタート地点、青い針＝現在地、青い点＝通った位置。b を n より大きくすると時計を何周もして、最後の「あまり」でオレンジの点に着地します。

POINT — 何周しても「あまり」は同じ (a + b) mod n は「a から b 歩進んで、n ごとに一周した残り」。時計（mod 12）だけでなく、曜日（mod 7）・角度（mod 360）・音階（mod 12）… 身のまわりは mod だらけです。回り込むおかげで、数がいくら大きくなっても 0〜n−1 の狭い範囲に収まり続けます。

(a + b) mod n 例）15時 = 15 mod 12 = 3時。時計は法 n = 12 の世界。n を法にした計算は、必ず 0〜n−1 の中に答えが返ってくる。

2. べき乗は時計の上を飛び回る — 周期が生まれる

足し算が「一定の歩幅で進む」動きなら、べき乗 g¹, g², g³, … mod p は「毎回 g 倍の位置へ跳ぶ」動きです。下のデモは、底 g をかけ続けた着地点を線で結んでいきます。素数 p の時計の上では、この跳躍がやがて出発点（1）に戻り、同じ軌跡をくり返します。この一巡りの長さが周期（位数）です。

底 g と法 p を変えて、跳ね回り方と周期の変化を見てください。ある g では全部の点を巡り、別の g ではごく短い周期でぐるぐる回ります。

べき乗の跳躍 — g^k mod p はどこへ着地するか

底 g

法 p（素数）

緑＝出発点（1 = g⁰）、線＝g をかけるたびの跳躍、オレンジ＝最新の跳び先。周期のぶんだけ跳ぶと必ず 1 に戻り、同じ模様を描き直します。g が原始根なら、全点を1度ずつ通る星形になります。

POINT — 原始根：全部の点を訪れる特別な底周期が p−1 に達する g を原始根と呼び、1 から p−1 まですべての点をちょうど一度ずつ踏んでから戻ります。跳び先はまるでランダムに散らばって見えるのに、実際は完全な規則で決まっている — この「規則的なのに次が読みにくい」性質が、次の一方向性の土台になります。

g^k mod p g を k 回かけて p で割ったあまり。k を1増やすと着地点は g 倍の位置へ跳び、円周のあちこちを跳ね回る。

3. 進むのは簡単、戻すのは大変 — 離散対数

ここが暗号の核心です。x を決めて g^x mod p を計算するのは一瞬（前向きは簡単）。ところが逆に、着地した点だけを見せられて「元の x はいくつ？」と問われると、手がかりは総当たりしかありません。この逆問題を離散対数問題と呼びます。下で前向き（x を動かす）と逆向き（点から x を探す）を切り替えてみてください。

前向きは一瞬、逆向きは総当たり — 離散対数

向き

指数 x

目標の点

前向きは指数 x を動かすと点がすぐ動きます（簡単）。逆向きは目標の点を決めると、k = 1, 2, 3, … と総当たりで指数を探します（大変）。ここでは p = 17 なので候補は16個だけですが、実際の素数は数百桁 — この探索は現実には終わりません。

注意 — 小さい時計では「難しさ」は見えない p = 17 なら候補はたった16個、しらみつぶしでも一瞬です。だが実際の暗号は数百桁の素数を使う。すると候補の数は宇宙の原子数をはるかに超え、前向き g^x は一瞬のままなのに、逆向きは事実上不可能になります。この「簡単な向き」と「絶望的な向き」の落差こそが、鍵を守る力の源です。

y = g^x mod p は簡単　／　x = log_g y (mod p) は困難これが一方向関数（片道の計算）。次のレッスンの鍵交換も RSA も、この非対称な落差の上に建っている。

4. まとめ — 片道の計算はどこから来るか

合同算術（mod）：n で割ったあまりだけを見る「時計の世界」。足し算は n を超えるとぐるっと回り込む。
べき乗 g^k mod p：毎回 g 倍の位置へ跳び、素数の時計ではやがて 1 に戻る（周期＝位数）。原始根なら全点を巡る。
一方向性：前向き g^x は一瞬、逆向き（離散対数）は総当たり。桁を大きくすると、この落差がそのまま暗号の強さになる。

一歩先へ — この「片道」が現代通信を支える時計の上の一見単純な跳躍が、インターネットの秘密をまるごと支えています。次の DH鍵交換は、まさに g^x mod p の「戻せなさ」を使って、盗聴者の目の前で秘密の鍵を作り出す魔法。RSA は素因数分解の一方向性を、楕円曲線暗号は曲線上の点の足し算で同じ離散対数の難しさを、より短い鍵で実現します。「あまりの世界」を先に押さえておくと、この先のレッスンがすべて地続きに見えてきます。