モジュロ計算機

モジュラ加算・減算・乗算・べき乗・逆元を計算。RSA暗号で使われるモジュラ演算を学びましょう。

基本モジュロ — モジュラ加算 — モジュラ減算 — モジュラ乗算 — モジュラべき乗 — モジュラ逆元 —

ガイド

詳しく見る

モジュロ演算(a mod m)は、a を m で割ったときの余りです。例:17 mod 5 = 2。時計の計算(24時間制)や曜日の計算など、日常でよく使われます。プログラミングでは配列インデックスの循環やハッシュ関数などに欠かせません。

モジュラ加算:(a + b) mod m。モジュラ乗算:(a × b) mod m。大きな数を計算する際のオーバーフローを防ぐには、各ステップごとにモジュロを取ります。例:(12 + 8) mod 5 = 20 mod 5 = 0。

a^b mod m を計算するとき、そのままべき乗すると数が大きくなりすぎます。分割統治法による高速べき乗アルゴリズムを使えば、O(log b) の時間で計算できます。RSA暗号の中核となる演算です。

モジュラ逆元は、(a × x) mod m = 1 となる x です。a と m が互いに素であるときにのみ存在します。拡張ユークリッドの互除法を用いて O(log m) の時間で計算します。復号や分数の計算に使われます。

RSAは、モジュラべき乗と逆元を中核とする公開鍵暗号システムです。暗号化:c = m^e mod n、復号:m = c^d mod n。2つの大きな素数の積 n を因数分解するのが難しいという性質を利用しています。