モジュラー演算

数学において、モジュラー演算は整数の演算システムであり、数値はモジュラスと呼ばれる特定の値に達すると「ラップアラウンド」します。モジュラー演算の現代的なアプローチは、1801年に出版されたカール・フリードリヒ・ガウスの著書『Disquisitiones Arithmeticae』で開発されました。

モジュラー演算のよく知られた使用法は、1 日を 2 つの 12 時間期間に分割する12 時間制時計です。現在時刻が 7:00 の場合、8 時間後には 3:00 になります。単純な加算では7 + 8 = 15となりますが、時計は 12 時間ごとに「一周」し、12 に達すると時間の数字がゼロから始まるため、15:00 は時計の文字盤上では 3:00 と表示されます。15 は 3 を法として 12 と同値であるとされ、15 ≡ 3 (mod 12) と表記されるため、7 + 8 ≡ 3 (mod 12) となります。同様に、8:00 は 8 時間の期間を表し、これを 2 回繰り返すと 16:00 となり、時計の文字盤上では 2 × 8 ≡ 4 (mod 12) と表記されて 4:00 となります。

整数 m ≥ 1 （法）が与えられたとき、2つの整数aとbは、 m がそれらの差の約数である場合、mを法として合同であると言われる。つまり 、

a − b = km です。

mを法とする合同は合同関係であり、加算、減算、乗算の演算と互換性のある同値関係であることを意味する。mを法とする合同は次のように表記される。

a ≡ b (mod m )。

括弧は、(mod m ) が右側の辺 (ここではb ) だけでなく、方程式全体に適用されることを意味します。

この表記を、モジュロ演算、つまりbをmで割った余りを表す表記b mod m (括弧なし) と混同しないでください。つまり、b mod m は、 0 ≤ r < mかつr ≡ b (mod m )となる一意の整数r を表します。

合同関係は次のように書き直すことができる。

a = km + b、

ユークリッドの除算との関係を明示的に示しています。しかし、ここでのb はaをmで割ったときの余りである必要はありません。むしろ、a ≡ b (mod m ) は、 aとb をmで割ったときの余りが同じであることを示しています。つまり、

a = pm + r、

b = qm + r、

ここで、0 ≤ r < m は共通の剰余です。これら 2 つの式を減算し、k = p − qと設定すると、前の関係 ( a − b = km ) が復元されます。

m を法とする合同性はmによる割り切れるかどうかで定義され、-1 は整数環の単位であるため、数がmで割り切れる場合は、その数は- mで割り切れます。つまり、ゼロ以外のすべての整数m を法として取ることができます。

モジュラス 12 では、次のことが言えます。

38 ≡ 14 (12 で割る)

なぜなら、その差は38 − 14 = 24 = 2 × 12であり、 12の倍数だからです。同様に、38と14を12で割った余りは2です。

合同の定義は負の値にも適用されます。例:

${\displaystyle {\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}$

合同関係は同値関係 のすべての条件を満たします。

• 反射性: a ≡ a (mod m )
• 対称性: b ≡ a (mod m )ならばa ≡ b (mod m )。
• 推移性: a ≡ b (mod m )かつb ≡ c (mod m )ならば、a ≡ c (mod m )

a ₁ ≡ b ₁ (mod m )かつa 2 _≡ b 2 ₍ mod m )、またはa ≡ b (mod m )の場合、次の式が成り立ちます。^[1]

• 任意の整数kに対してa + k ≡ b + k (mod m )（翻訳との互換性）
• ka ≡ kb (mod m )任意の整数kに対して(スケーリングとの互換性)
• ka ≡ kb (mod km )任意の整数kに対して
• a ₁ + a ₂ ≡ b ₁ + b ₂ (mod m ) (加算との互換性)
• a ₁ − a ₂ ≡ b ₁ − b ₂ (mod m ) (減算との互換性)
• a ₁ a ₂ ≡ b ₁ b ₂ (mod m ) (乗算との互換性)
• 任意の非負整数kに対してa ^k ≡ b ^k (mod m )（べき乗法と互換性あり）
• p ( a ) ≡ p ( b ) (mod m )、整数係数を持つ任意の多項式 p ( x )に対して（多項式評価との互換性）

a ≡ b (mod m )の場合、 k ^a ≡ k ^b (mod m )は一般に誤りです。ただし、次のことは当てはまります。

• c ≡ d (mod φ ( m ))の場合、φはオイラーのトーシェント関数であり、a ^c ≡ a ^d (mod m )です。ただし、a はmと互いに素です。

共通規約の解約については、以下の規定があります。

• a + k ≡ b + k (mod m ) （ kは任意の整数）の場合、a ≡ b (mod m )です。
• ka ≡ kb (mod m )かつkがmと互いに素である場合、a ≡ b (mod m )です。
• ka ≡ kb (mod km )かつk ≠ 0の場合、a ≡ b (mod m )です。

最後の規則は、モジュラー演算を除算に移行するために使用できます。b がa を割り切る場合、( a / b ) mod m = ( a mod bm ) / b となります。

モジュラー逆乗法は次の規則によって定義されます。

• 存在: a ⁻¹で表される整数が存在し、 aa ⁻¹ ≡ 1 (mod m )となるのは、 a がmと互いに素である場合に限ります。この整数a ^{−1 は、}aを法としてmのモジュラー逆数と呼ばれます。
• a ≡ b (mod m )かつa ⁻¹が存在する場合、a ⁻¹ ≡ b ⁻¹ (mod m )である（乗法逆数との互換性があり、a = bの場合、mを法として一意である）。
• もしax ≡ b (mod m )かつaがmと互いに素であれば、この線型合同の解はx ≡ a ⁻¹ b (mod m )で与えられます。

逆数x ≡ a ⁻¹ (mod m )は、拡張ユークリッド互除法を用いて、ベズー方程式 a x + my = 1 をx、yに対して 解くことで効率的に計算できます。

特に、pが素数の場合、0 < a < pとなるすべてのaについて、 a はpと互いに素です。したがって、 pを法としてゼロと合同でないすべてのaに対して、逆数が存在します。

合同関係のより高度な特性のいくつかは次のとおりです。

• フェルマーの小定理: p が素数であり、 a を割り切れない場合、a ^{p −1} ≡ 1 (mod p )です。
• オイラーの定理: aとm が互いに素である場合、a ^{φ ( m )} ≡ 1 (mod m )であり、ここでφはオイラーのトーシェント関数です。
• フェルマーの小定理の簡単な帰結は、pが素数であれば、a ⁻¹ ≡ a ^{p −2} (mod p )は0 < a < pの逆数であるということです。より一般的には、オイラーの定理から、aとmが互いに素であれば、a ⁻¹ ≡ a ^{φ ( m )−1} (mod m )です。したがって、ax ≡ 1 (mod m )であれば、x ≡ a ^{φ ( m )−1} (mod m )です。
• もう1つの単純な帰結は、φがオイラーのトーシェント関数であるとき、 a ≡ b (mod φ ( m ))の場合、 kがmと互いに素であれば、k ^a ≡ k ^b (mod m )となるということです。
• ウィルソンの定理: pが素数であるためには、( p − 1)! ≡ −1 (mod p )を満たす必要があります。
• 中国剰余定理: 任意のa、b および互いに素なm、nに対して、 x ≡ a (mod m )かつx ≡ b (mod n )となる唯一のx (mod mn )が存在する。実際、 x ≡ bm _n ⁻¹ m + an _m ⁻¹ n (mod mn )であり、ここでm _n ^−1はn を法とするmの逆数であり、n _m ^{−1 は}m を法とするnの逆数である。
• ラグランジュの定理: p が素数であり、f ( x ) = a ₀ x ^d + ... + a _dが整数係数を持つ多項式で、 p がa ₀の約数でない場合、合同式f ( x ) ≡ 0 (mod p ) には最大d 個の非合同解が存在します。
• m を法とする原始根: 数g がmを法とする原始根であるとは、mと互いに素なすべての整数aに対して、 g ^k ≡ a (mod m )となる整数kが存在する場合をいいます。mを法とする原始根が存在するのは、 m が2、4、p ^k、または2 p ^kに等しい場合のみです。ここでpは奇数の素数で、k は正の整数です。m を法とする原始根が存在する場合、そのような原始根はちょうどφ ( φ ( m ))個存在します。ここでφはオイラーのトーシェント関数です。
• 平方剰余: 整数a がm を法とする平方剰余であるとは、 x ² ≡ a (mod m )となる整数x が存在する場合である。オイラーの基準によれば、p が奇数の素数でa がpの倍数でない場合、a がp を法とする 平方剰余となるのは、

  ^{p −1/2} ≡ 1 (mod ^p )です。

合同関係は同値関係です。整数aのm を法とする同値類は、形式a + kmのすべての整数の集合です。ここで、kは任意の整数です。これは、 m を法とする aの合同類または剰余類と呼ばれ、 ( a mod m )と表記されるか、法m が文脈からわかっている 場合はaまたは[ a ]と表記されます。

mを法とする各剰余類には 、範囲内の整数が 1 つだけ含まれます。したがって、これらの整数はそれぞれの剰余類を 表します。${\displaystyle 0,...,|m|-1}$${\displaystyle |m|}$

一般に、整数の集合よりも整数を扱う方が簡単です。つまり、剰余類よりも、最も頻繁に考慮される代表値を扱う方が簡単です。

したがって、( a mod m )は一般に、 0 ≤ k < mかつk ≡ a (mod m )となる唯一の整数kを表します。これはaを法とする mの剰余と呼ばれます。

特に、( a mod m ) = ( b mod m )はa ≡ b (mod m )と同等であり、この文脈では「 ≡ 」の代わりに「 = 」がよく使用されるのはそのためです。

mを法とする各剰余類は、そのメンバーのいずれかで表すことができますが、通常は各剰余類をそのクラスに属する最小の非負整数で表します^{[2] （これが除算から得られる適切な剰余であるため）。} m を法とする異なる剰余類の任意の 2 つのメンバーは、m を法として不同です。さらに、すべての整数は、 mを法とする 1 つの剰余類にのみ属します。^[3]

整数の集合{0, 1, 2, ..., m − 1}は、 m を法とする最小剰余系と呼ばれます。 m個の整数の集合のうち、どの 2 つもm を法として合同でないものはすべて、 m を法とする完全剰余系と呼ばれます。

最小剰余系は完全剰余系であり、完全剰余系は単に、mを法として各剰余類の代表を1 つだけ含む集合である。^{[4]たとえば、} 4を法として最小剰余系は{0, 1, 2, 3}である。 4を法として他の完全剰余系には以下のものがある。

• {1、2、3、4}
• {13、14、15、16}
• {−2, −1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27、32、37、42}

4 を法とする完全剰余系 ではない集合には次のようなものがあります。

• {−5, 0, 6, 22}、6は4を法として22と合同であるため。
• {5, 15} 、 4を法とする完全な剰余系は、正確に4つの不一致な剰余類を持つ必要があるため。

オイラーのトーシェント関数 φ ( m )が与えられたとき、mと互いに素で、かつ法mに関して互いに不同であるφ ( m )個の整数の任意の集合は、法mの縮約剰余系と呼ばれる。^[5]例えば、上記の集合{5, 15}は、法 4 の縮約剰余系の一例である。

被覆システムは、さまざまな係数を持つ残基を含む可能性のある、さらに別のタイプの残基システムを表します。

注: この段落の文脈では、係数m はほぼ常に正の値として扱われます。

mを法とする合同類全体の成す集合は、m を法とする整数環^[6]と呼ばれ、 、、または と表記される。^[7]ただし、この表記はm進整数の集合と混同される可能性があるため推奨されない。環は数学のさまざまな分野の基礎となる（以下の§ 応用を参照）。 ${\textstyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m}$${\displaystyle \mathbb {Z} _{m}}$${\displaystyle \mathbb {Z} _{m}}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

m > 0 の場合、

${\displaystyle \mathbb {Z} /m\mathbb {Z} =\left\{{\overline {a}}_{m}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{m},{\overline {1}}_{m},{\overline {2}}_{m},\ldots ,{\overline {m{-}1}}_{m}\right\}.}$

m = 1 のとき、 は零環です。m = 0 のとき、は空集合ではありません。むしろ、 a ₀ = { a }なので、と同型です。 ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} }$

加算、減算、乗算は次の規則によって定義されます。 ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

• ${\displaystyle {\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.}$

前述の性質から、これらの演算により、 は可換環であることが分かる。例えば、環 では、 ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /24\mathbb {Z} }$

${\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}}$

24 時間制の計算の場合と同様です。

表記法が使用されるのは、この環がイデアル による商環であり、すべてのkmが${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} }$ ${\displaystyle m\mathbb {Z} }$${\displaystyle k\in \mathbb {Z} .}$

加法群として考えると、巡回群であり、すべての巡回群は、あるmに対してと同型である。^[8]${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

m を法とする整数の環が体となるのは、 mが素数である場合に限ります（これにより、すべての非ゼロの元に逆元 が存在することが保証されます）。m = p k が k > 1 の素数冪である場合、 m個^の元を持つ一意の（同型を除いて）有限体が存在しますが、これはと同型ではなく、零因子 を持つため体になることができません。 ${\displaystyle \mathrm {GF} (m)=\mathbb {F} _{m}}$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

m > 1の場合、逆元となるmを法とする整数の乗法群を表します。これは、aがmと互いに素である合同類a _mで構成されます。これらはまさに乗法逆元を持つ類です。これらは乗法に関してアーベル群を形成します。その位数はφ ( m )で、φはオイラーのトーシェント関数です。${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$

純粋数学において、モジュラー算術は数論の基礎の 1 つであり、数論の研究のほぼすべての側面に関係しており、群論、環論、結び目理論、抽象代数学でも広く使用されています。応用数学では、コンピュータ代数、暗号学、コンピュータサイエンス、化学、視覚芸術、音楽芸術で使用されています。

非常に実用的なアプリケーションは、シリアル番号識別子内のチェックサムを計算することです。たとえば、国際標準図書番号(ISBN) は、エラー検出にモジュロ 11 (10 桁の ISBN の場合) またはモジュロ 10 (13 桁の ISBN の場合) の演算を使用します。同様に、たとえば国際銀行口座番号(IBAN) は、銀行口座番号のユーザー入力エラーを見つけるためにモジュロ 97 の演算を使用します。化学では、CAS 登録番号(各化合物の一意の識別番号)の最後の桁がチェック ディジットです。これは、CAS 登録番号の最初の 2 つの部分の最後の桁に 1 を掛け、その前の桁に 2 を掛け、その前の桁に 3 を掛けるなどして、これらすべてを加算し、モジュロ 10 の合計を計算します。

暗号化において、モジュラー演算はRSAやDiffie-Hellmanなどの公開鍵システムの直接的な基盤となっており、楕円曲線の基礎となる有限体を提供するほか、 Advanced Encryption Standard (AES)、International Data Encryption Algorithm (IDEA)、RC4などのさまざまな対称鍵アルゴリズムで使用されています。RSA と Diffie-Hellman はモジュラー指数演算を使用しています。

コンピュータ代数では、モジュラー演算は中間計算やデータにおける整数係数のサイズを制限するためによく使用されます。これは多項式因数分解で使用され、この問題に対する既知の効率的なアルゴリズムはすべてモジュラー演算を使用しています。これは、多項式最大公約数、正確な線形代数、および整数と有理数に対するグレブナー基底アルゴリズムの最も効率的な実装で使用されています。 1980年代にFidonetに投稿され、 Rosetta Codeにアーカイブされているように、モジュラー演算は、20年前にブルートフォース検索でオイラーの累乗和予想を反証するために使用されたCDC 6600スーパーコンピュータで使用された整数精度のわずか4分の1を使用して、シンクレアQLマイクロコンピュータでオイラーの累乗和予想を反証するために使用されました。^[9]

コンピュータ サイエンスでは、モジュラー演算はビット演算や、固定幅の循環データ構造を伴うその他の演算によく適用されます。多くのプログラミング言語や計算機で実装されているモジュロ演算は、このコンテキストでよく使用されるモジュラー演算の応用です。論理演算子XOR は、2 ビットを 2 で割って合計します。

長除法を使用して分数を任意の基数 b の循環小数に変換することは、分母を法とする b のモジュラー乗算と同等です。たとえば、小数の場合、b = 10 です。

音楽では、12 を法とする算術は、オクターブと異名同音が等価となる (つまり、1:2 または 2:1 の比率のピッチは等価であり、CシャープはDフラットと同じであると見なされる) 十二音平均律のシステムを考慮する際に使用されます。

9 を除外する方法は、手作業で実行される 10 進数の計算をすばやくチェックできます。これは、9 を法とするモジュラー演算、特に 10 ≡ 1 (mod 9) という重要な特性に基づいています。

7 を法とする演算は、特定の日付の曜日を決定するアルゴリズムで使用されます。特に、ツェラーの合同法とDoomsday アルゴリズムでは、7 を法とする演算が多用されます。

より一般的には、モジュラー演算は、法律（例：配分）、経済学（例：ゲーム理論）、およびリソースの比例分割と割り当てが分析の中心的な役割を果たす社会科学のその他の領域などの分野にも応用されています。

モジュラー演算の応用範囲が広いため、合同式を解くのがいかに難しいかを知っておくことが重要です。線形合同式は、ガウス消去法の一種を使用して多項式時間で解くことができます。詳細については、線形合同定理を参照してください。モンゴメリ減算などのアルゴリズムも存在し、乗算やmを法とする累乗 などの単純な算術演算を大きな数に対して効率的に実行できます。

離散対数や二次合同を求めるなどの一部の演算は、整数因数分解と同じくらい難しいように思われ、そのため暗号化アルゴリズムや暗号化の出発点となっています。これらの問題はNP 中間問題である可能性があります。

非線形モジュラー算術方程式系を解くことはNP完全である。^[10]

• John L. Berggren. 「モジュラー算術」。ブリタニカ百科事典。
• アポストル、トム・M. (1976)、解析的数論入門、数学の学部テキスト、ニューヨーク-ハイデルベルグ：シュプリンガー・フェアラーク、ISBN 978-0-387-90163-3、MR  0434929、Zbl  0335.10001基本的なモジュラー演算の復習については、特に第 5 章と第 6 章を参照してください。
• マールテン・ブリンク「CFガウス以前のモジュラー算術。18世紀ドイツにおける剰余問題の体系化と議論」
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション31.3 :モジュラー演算、pp. 862–868。 
• アンソニー・ジョイア『数論入門』再版（2001年）ドーバー。ISBN 0-486-41449-3。 
• ロング、カルビン T. (1972)。『初等数論入門』（第 2 版）。レキシントン: DC Heath and Company。LCCN 77171950  。
• ペットフレッツォ、アンソニー J.; バーキット、ドナルド R. (1970)。数論の要素。イングルウッド クリフス:プレンティス ホール。ISBN 9780132683005LCCN  71081766 。
• Sengadir, T. (2009).離散数学と組合せ論. チェンナイ、インド: Pearson Education India. ISBN 978-81-317-1405-8. OCLC  778356123.

• 「合同性」、数学百科事典、EMS Press、2001 [1994]
• このモジュラー アートの記事では、モジュラー算術のアートへの応用について詳しく学ぶことができます。
• GIMPS wiki のモジュラー演算に関する記事
• モジュラー算術と加算と乗算の表のパターン