モジュロ演算

RFC 6090 モジュロ演算

10進数が9の次が10で繰り上がり1桁目が0に戻るのと同じように、特定の大きい数を超えると0に戻る計算のルール

デジタルの数値もビット数などで上限が出てきたりするので暗合などに使われる。

割り算の余りの概念

表記上の1桁ではなく全体で1桁と捉えてもよし

RFC 6090 Section 2

2.1 合同算術(合同式、モジュロ演算 剰余演算, Modular Arithmetic)

この節では、モジュロ演算(剰余演算)について概説する。2つの整数 x と y は、x - y が n の整数倍であるとき、n を法として合同であると言われる。

2つの整数 x と y は、それらの最大公約数が 1 であるとき互いに素である。この場合、z が x を割り切り、かつ z が y を割り切るような、z > 1 である3番目の数は存在しない。

集合 Zq = { 0, 1, 2, ..., q-1 } は、モジュラー加算、モジュラー減算、モジュラー乗算、およびモジュラー逆演算に関して閉じている。これらの演算は以下のとおりである。

Zq 内の整数 a と b の各ペアについて、a + b mod q は、a + b < q のときは a + b に等しく、それ以外のときは a + b - q に等しい。

Zq 内の整数 a と b の各ペアについて、a - b mod q は、a - b >= 0 の場合には a - b に等しく、それ以外の場合には a - b + q に等しい。

Zq 内の整数 a と b の各ペアについて、a * b mod q は、a * b を q で割った余りに等しい。