モジュロ演算入門：基礎、性質、アルゴリズム、暗号応用

2025年11月27日 最終更新日時 : 2025年11月27日 エバープレイ編集部

はじめに

モジュロ演算（剰余算）は、整数論やアルゴリズム、暗号、ハッシュ関数、符号理論など IT の広範な分野で基礎となる概念です。日常的な「時計算」から、RSA のような公開鍵暗号、効率的な累乗計算まで、さまざまな応用があります。本コラムではモジュロ演算の定義から性質、主要な定理、アルゴリズム、実装上の注意点、応用例までを詳しく解説します。ファクトチェック済みの定理・アルゴリズムを中心に、実践で気をつけるポイントも提示します。

モジュロ演算とは（定義と直感）

整数 a を正の整数 n で割ったときの余り r（0 ≤ r < n）を表す操作が剰余（modulo）です。記号では次のように書きます。

  • a ≡ b (mod n) ： a と b は n を法として合同（つまり n が a−b を割る）
  • a mod n = r ： a = qn + r（q は商、r は余り）

例えば 17 mod 5 = 2、かつ 17 ≡ 2 (mod 5)。時計の12時間表記は 12 を法とするモジュロ演算の直感的な例です。

合同式の基本性質

合同関係は同値関係（反射律、対称律、推移律）を満たします。重要な演算則は次のとおりです（m は法、gcd は最大公約数）。

  • 加法：もし a ≡ b (mod m) と c ≡ d (mod m) ならば a+c ≡ b+d (mod m)
  • 減算：a−c ≡ b−d (mod m)
  • 乗算：a·c ≡ b·d (mod m)
  • 累乗：a ≡ b (mod m) ならば a^k ≡ b^k (mod m)（k は非負整数）

ただし除算は注意が必要です。a·x ≡ a·y (mod m) から x ≡ y (mod m) が成り立つためには、a と m が互いに素（gcd(a,m)=1）でなければなりません。

剰余類と環・群としての構造

整数全体を n を法で割ったときの剰余類に分けると、Z/nZ（ゼット・オーバー・エヌ）という代数構造になります。加法と乗法を法で取ることで、Z/nZ は環になります。さらに互いに素な元のみを考えると、(Z/nZ)^×（乗法群）を得ます。

  • 単元（逆元を持つ要素）：a が逆元を持つ ⇔ gcd(a,n)=1
  • 位数：ある a の最小の正整数 k で a^k ≡ 1 (mod n)

特に n が素数 p のとき、Z/pZ は体（field）になり、(Z/pZ)^× はサイズ p−1 の巡回群になることが多く、フェルマーの小定理や原始根の存在が使えます。

重要な定理（フェルマー・オイラー・中国剰余）

  • フェルマーの小定理：p を素数、a を p で割り切れない整数とすると a^{p-1} ≡ 1 (mod p)。これにより a^k の剰余を簡約できます。
  • オイラーの定理：gcd(a,n)=1 のとき a^{φ(n)} ≡ 1 (mod n)。φ(n) はオイラーのトーシェント関数（1～n のうち n と互いに素な数の個数）です。
  • 中国剰余定理（CRT）：互いに素な法 n1,…,nk に対して連立合同式 x ≡ a_i (mod n_i) は一意な解を N=∏ n_i を法として持ちます。非互いに素の場合は互換性条件（各 i,j について a_i ≡ a_j (mod gcd(n_i,n_j))）が必要です。

逆元と拡張ユークリッドのアルゴリズム

モジュロ逆元 x を求める問題は、a·x ≡ 1 (mod n) を解くことに相当します。解が存在するのは gcd(a,n)=1 のときのみで、このとき拡張ユークリッドアルゴリズムを使うと x を O(log n) 回の除算で求められます。手順は次の通りです。

  • 拡張ユークリッドで ax + ny = gcd(a,n)=1 を求める。
  • そのときの x を法 n で正規化すれば a の逆元になる。

高速べき乗（モジュラ累乗）

累乗 a^e mod n を直接計算すると指数の大きさに比例するため現実的でありません。二分累乗法（反復二乗法、binary exponentiation）を用いれば O(log e) の乗算で計算できます。基本アイデアは指数を二進表現に分解して、繰り返し自乗と条件付き乗算を行うことです。ほとんどの言語やライブラリに実装があるか、自力で簡潔に実装できます。

中国剰余定理の応用と実装

CRT は複数の小さな法で計算した結果を大きな法へ合成するのに便利です。実装方法はいくつかありますが、代表的なのは次の手順です。

  • N = ∏ n_i を計算する。
  • 各 i について N_i = N / n_i を計算し、N_i の n_i における逆元 M_i を求める。
  • x = Σ a_i · N_i · M_i を計算し、N で剰余を取る。

法が互いに素でない場合は先に互換性をチェックし、必要なら方程式をマージしていく「一般化CRT」を用います。大きな数での構成は計算誤差やオーバーフローに注意し、任意精度整数（bigint）を使うのが無難です。

数論的概念：位数・原始根・二次剰余

位数は群論的観点から重要で、a の位数 d は a^d ≡ 1 となる最小の正整数です。位数は φ(n) を割ります。原始根（generator, primitive root）は (Z/pZ)^× が巡回群である場合に存在し、位数が最大（p−1）となる元です（全ての素数 p に原始根が存在することは別途の定理）。

二次剰余は x^2 ≡ a (mod p) が解を持つかどうかを扱います。ルジャンドル記号 (a|p) や二次補法則が用いられ、暗号理論（例：平方剰余の決定やプロトコル）に応用されます。

暗号における利用例（RSA 等）

RSA 暗号はモジュロ演算の典型的な応用です。公開鍵は (N=eの法? ではなく) N=pq（大きな合成数）と公開指数 e、秘密鍵は d（ed ≡ 1 (mod φ(N))）です。暗号化は c ≡ m^e (mod N)、復号は m ≡ c^d (mod N) によって行われます。ここでの安全性は φ(N) を効率良く求められない（つまり p,q を因数分解できない）ことに依存します。

ほかにも、ディフィー・ヘルマン鍵共有、デジタル署名、ハッシュ関数の一部アルゴリズムでもモジュラ演算は不可欠です。

実装上の注意点（言語別の振る舞い、負数、オーバーフロー）

プログラミングでモジュロ演算を扱う際の注意点：

  • 言語によって負の数の剰余の扱いが異なる（例：C/C++は実装定義や言語仕様に依存、Python は負数でも非負の剰余を返す）。負の値から正の剰余を得るには (a % n + n) % n のように正規化するのが安全です。
  • 乗算によるオーバーフローに注意。固定長整数を用いる場合は一旦 128 ビットや任意精度整数に拡張するか、乗算を分割するテクニックを使う。多くの言語は big integer ライブラリを提供している。
  • モジュラ乗算を高速化する方法として、Montgomery 乗算や Barrett 削除などがある。大きなモジュロを多数回扱う暗号実装ではこれらが必須となることが多い。

アルゴリズム的複雑度

基本的な計算の時間計算量の概念：

  • 拡張ユークリッドアルゴリズム：O(log n)（各ステップでの除算）
  • 高速べき乗：O(log e) 乗算（1回の乗算のコストは数の桁数に依存）
  • CRT の合成：モジュロ間の数の乗算や逆元計算がボトルネック。k 個のモジュロを合成する場合はおおむね O(k) の逆元計算と数回の大数乗算が必要。

ここでの『乗算コスト』は大数乗算アルゴリズム（Karatsuba、FFT ベースなど）に依存します。大規模暗号では数百〜数千ビットの演算が要求され、実装は高度に最適化されます。

実用的な落とし穴と対策例

  • 素朴な剰余計算での負の値扱い：常に結果を 0..n-1 の範囲に正規化する。
  • 累乗の指数が非常に大きい場合：オイラーの定理やフェルマーを使って指数を法（φ(n)や p−1）で縮約できる場面がある。ただし gcd(a,n)≠1 の場合は注意が必要。
  • 並列化・分散化：CRT を使って大きな累乗を小さな法の組に分割して計算し、最後に合成することで効率化できる（ただし通信コストと整合性に注意）。

まとめ

モジュロ演算は単純に見えて深い理論と多様な応用を持ちます。基本的な合同式の性質、拡張ユークリッドによる逆元、オイラーやフェルマーの定理、CRT、そして高速べき乗やMontgomery 乗算といった実装技術を理解することで、暗号や大数計算、アルゴリズムの安全性・効率性を高められます。実装では言語固有の仕様やオーバーフロー、負数処理に気をつけ、必要に応じて既存の確立された数値ライブラリを使うことを推奨します。

参考文献

カテゴリー
IT
前の記事
XR（拡張現実）の全貌：技術・ユースケース・課題と今後の展望New!!
2025年11月27日