モジュロ計算機

割り算の余りを求める基本のモジュロ演算に加え、モジュラー加算・減算・乗算・べき乗・逆元をワンストップで計算できます。

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

ガイド

詳しく見る

モジュロ演算とは何か

モジュロ演算(a mod m)は、aをmで割ったときに残る余りを求める計算です。例えば17 mod 5は2になります。時計の針が12を超えると1に戻るように、一定の周期でループする値を扱うのが得意で、曜日の計算やアナログ時計の表示など身近な場面でも自然に使われています。プログラミングの世界では、配列のインデックスを循環させたり、ハッシュテーブルの格納先を決めたりする際に欠かせない演算です。

モジュラー加算・減算・乗算の考え方

モジュラー加算は(a + b) mod m、モジュラー減算は(a − b) mod m、モジュラー乗算は(a × b) mod mという形で表されます。桁数の大きな数をそのまま扱うと計算が重くなったり桁あふれが起きたりするため、各ステップの途中でこまめにモジュロを取ることで数値を小さく保ちながら正確な結果を得られます。例えば(12 + 8) mod 5を計算すると、20 mod 5となり答えは0です。

モジュラーべき乗を高速に求める方法

a^b mod mを求めたいとき、a^bを先に計算してしまうと数字が天文学的な大きさに膨れ上がってしまいます。そこで使われるのが「繰り返し二乗法」と呼ばれる分割統治のアルゴリズムで、指数を2で割りながら計算を進めることでO(log b)という非常に短い時間で答えにたどり着けます。この仕組みはRSA暗号の暗号化・復号処理の核となっており、実務でも頻繁に登場します。

モジュラー逆元と拡張ユークリッドの互除法

モジュラー逆元とは、(a × x) mod m = 1を満たすxのことを指し、aとmの最大公約数が1(互いに素)である場合にのみ存在します。拡張ユークリッドの互除法を使えばO(log m)の時間で効率よく求められ、暗号の復号処理や分数を扱う計算の中で活躍します。互いに素でない組み合わせ、例えばaもmも偶数であるような場合には、逆元は存在しないため注意が必要です。

RSA暗号を支えるモジュラー演算

RSAはモジュラーべき乗とモジュラー逆元を組み合わせた公開鍵暗号方式です。暗号化はc = m^e mod n、復号はm = c^d mod nという式で表され、非常に大きな2つの素数の積であるnを因数分解するのが極めて困難であるという数学的事実を安全性の根拠にしています。この計算機で使われている剰余演算・べき乗・逆元の各機能は、実際のRSA暗号の内部でも同じ原理で動いています。

よくある質問

負の数をモジュロ計算するとどうなりますか？

負の数の扱いはプログラミング言語によって異なりますが、この計算機は数学的な定義に従い、結果が常に0以上m未満になるよう計算します。例えば-7 mod 5の答えは3です。

法(m)に0を入力するとどうなりますか？

0で割ることは数学的に定義されていないため、法に0を入力すると計算できません。mは1以上の整数を入力してください。

モジュラー逆元が存在しないのはどんなときですか？

aとmの最大公約数が1でない場合、つまり互いに素でない場合にはモジュラー逆元は存在しません。例えばmが偶数でaも偶数であれば、逆元を求めることはできません。

モジュラーべき乗になぜ高速なアルゴリズムが必要なのですか？

指数が大きくなるとa^bの値自体が桁違いに大きくなり、そのまま計算するのは非現実的です。繰り返し二乗法を使えば各ステップでモジュロを取って数を小さく保ちながら、O(log b)という短い時間で結果を導けます。

この計算機は実際にどのような場面で役立ちますか？

ハッシュテーブルの格納先を決める計算、曜日や時刻のような周期的なスケジュール管理、RSAをはじめとする公開鍵暗号の暗号化・復号処理、ISBNなどのチェックディジット検証など、幅広い場面で剰余演算が使われています。