合同式（モジュラー演算）計算機とは？
モジュラー演算は、よく「時計算」にたとえられます。数値は法（モジュラス）n に達するとリセットされ、ぐるりと一周して戻ってくる仕組みです。この計算機は \((\text{a} \text{ op } \text{b}) \bmod \text{n}\) という形の式を計算します。演算には加算・減算・乗算のほか、単一の値 a を法 n で割った余りを求めるだけのモードも選べます。結果は常に 0 以上で最小の剰余、つまり 0 から n − 1 までの範囲の数値で返されます。
使い方
まず a に値を入力し、演算を選び、b を指定します（「mod のみ」の場合 b は無視されます）。最後に法 n を設定してください。計算機はまず式そのものを計算し、その結果を n で割った剰余に変換します。負の結果は 0…n−1 の標準的な範囲に折り返されるため、たとえば \(-1 \bmod 12\) は −1 ではなく 11 を返します。
計算式の解説
基本となる関係式は \(r = (\text{a} \text{ op } \text{b}) \bmod \text{n}\) です。プログラミングで使われる剰余演算は負の値を返すことがあるため、ここでは次の「ユークリッド型」の形を用い、必ず 0 以上の答えになるようにしています。
$$r = ((x \bmod \text{n}) + \text{n}) \bmod \text{n}$$これは整数論・暗号理論・ハッシュ計算などで標準的に使われる数学的な約束ごとと一致します。
具体例
たとえば a = 17、演算は加算、b = 25、n = 12 とします。まず $$17 + 25 = 42$$ を計算します。次に \(42 \bmod 12\) を求めると、\(42 = 3 \times 12 + 6\) なので剰余は 6 です。12 時間制の時計でいえば、17 時から 25「時間」進むと、ちょうど 6 の位置に来るということです。
よくある質問
「mod」とは何ですか？ 割り算をした後の「余り」を返す演算です。\(13 \bmod 5 = 3\) となるのは、\(13 = 2 \times 5 + 3\) だからです。
なぜ負の数が正の数に変わるのですか？ この計算機は 0 以上で最小の剰余を返すためです。たとえば \(-7 \bmod 5 = 3\) となります。これは 5 を 2 回足すと（\(-7 + 10 = 3\)）、ちょうど 0…4 の範囲に収まるからです。
n = 1 のときはどうなりますか？ すべての整数は法 1 において 0 と合同なので、結果は常に 0 になります。
