| 余り r | 商 q | 乗数 t |
|---|
モジュラー時計
9時の5時間後は2時です。9 + 5 = 14 で、14は12より2大きいからです。これが合同算術、つまり n を過ぎると再び0から始まる時計の上で数えることです。演算を選んで n、a、b を入力すると、計算機が割り算の余りから繰り返し二乗法や拡張ユークリッドの互除法まで、すべてのステップを書き出して答えを示し、同時に時計が答えにたどり着くまでの様子を表示します。 演算を選び、法 n と数 a、b を入力してください。30桁までの整数が使え、負の数も扱え、n は10^18まで指定できます。時計には n 個の位置があって0が一番上にあり、針が答えを指します。足し算と引き算は b 歩のらせんとして描かれ、1周するごとに輪が1つ増えます。掛け算は a ずつのジャンプとして、累乗は閉じて1つのサイクルになる弦 a, a², a³ … として、逆数と割り算は1または a に着地する倍数として描かれます。ステップでは同じ計算を数で示します。mod 20までは演算表が表示され、マスをクリックするとその数を使えます。「例」を選ぶと古典的な問題が入力されます。
使い方
- 演算を選びます:a mod n、足し算、引き算、掛け算、割り算、累乗、または a の逆数。
- 法 n と数 a、b を入力するか、7^2026 の一の位や小さな RSA メッセージなどの例を選びます。
- 答えとステップを読み、時計の上の道のりをたどります。mod 20までは表のマスをクリックしてその数を試せます。
a mod n の意味
a mod n は a を n で割ったときの余りです。17 = 3 × 5 + 2 なので、17 mod 5 = 2 です。余りは負の数の場合も含めて常に0から n − 1 までです:−7 = −3 × 3 + 2 なので、−7 mod 3 = 2 です。時計の上では、0から7歩戻ることを意味します。同じ余りを持つ2つの数は合同であるといい、17 ≡ 2 (mod 5) と書きます。この記法は1801年にカール・フリードリヒ・ガウスが導入しました。和・差・積はどのステップでも n を法として簡約でき、そうすれば数が小さいまま保たれます。
合同算術が使われる場面
時計とカレンダーは mod 12、mod 24、mod 7 で動いています:100 mod 7 = 2 なので、水曜日の100日後は金曜日です。チェックディジットは入力ミスを見つけるためにこれを使っており、ISBN-10(mod 11)から銀行カードの番号(mod 10)、IBAN(mod 97)まで幅広く使われています。暗号は文字を mod 26 でずらし、アフィン暗号の復号には mod 26 での逆数が必要です。インターネットの多くを守る RSA は、メッセージ m を m^e mod n として暗号化し、別の累乗で復号します:n = 3233 のとき、65^17 mod 3233 = 2790、2790^413 mod 3233 = 65 です。
よくある質問
負の数の a mod n はどう計算しますか?
数が0から n − 1 の間に入るまで、n の倍数を足すか引きます。−7 mod 3 なら、−7 + 9 = 2 なので答えは2です。プログラミング言語の中には、商を0に向けて丸めるため、−7 % 3 に対して代わりに −1 を返すものもあります。数学では余りが負になることはありません。
モジュラ逆数とは何ですか?
n を法とする a の逆数とは、a × x ≡ 1 (mod n) を満たす数 x のことです。7 × 15 = 105 = 4 × 26 + 1 なので、mod 26 での7の逆数は15です。逆数は a と n に共通の因数がないときにだけ存在し、拡張ユークリッドの互除法で求められます。n を法として a で割ることは、その逆数を掛けることを意味します。
7^2026 のような累乗を mod n でどう計算できますか?
繰り返し二乗法を使います。7を何度も二乗し、そのたびに n を法として簡約して 7^1、7^2、7^4、7^8 などを求め、2026を2進数で表したときに必要なものを掛け合わせます。これなら2,025回の掛け算の代わりに10回の二乗と7回の掛け算で済み、数が n² より大きくなることもありません。7^2026 の一の位は9です。
なぜ時計に12ではなく0が表示されるのですか?
合同算術では余りは0から n − 1 までなので、12個の位置がある時計では正午が0になります。12 ≡ 0 (mod 12) であり、普通の時計は数学で0と書くところに12と表示しているだけです。
どれくらい大きな数を扱えますか?
a と b は最大30桁で負の数も使え、法は10^18まで指定できます。計算機はブラウザー内で正確な整数を使って計算するため、RSA 規模の例でも正確な答えが得られ、どこにも何も送信されません。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ