モジュロ

コンピューターにおいて、モジュロ演算は、ある数値を別の数値で割った後の剰余または符号付き剰余を返します。この剰余は、演算の モジュラスと呼ばれます。

2つの正の数aとn が与えられたとき、nを法とするa（しばしばa mod nと略される）は、aをnでユークリッド除算した剰余である。ここで、 aは被除数、n は除数である。^[1]

たとえば、式「5 mod 2」は 1 と評価されます。これは、5 を 2 で割ると商が 2 で余りが 1 になるためです。一方、「9 mod 3」は 0 と評価されます。これは、9 を 3 で割ると商が 3 で余りが 0 になるためです。

通常はaとnの両方が整数である場合に実行されますが、現在では多くのコンピューティング システムで他の種類の数値オペランドが許可されています。nを法とする整数演算の値の範囲は0 からn − 1です( a mod 1 は常に 0 であり、a mod 0は未定義で、ゼロ除算です)。

aまたはnのいずれかが負の場合、基本的な定義は崩れ、プログラミング言語によってこれらの値の定義方法が異なります。

数学では、モジュロ演算の結果は同値類であり、そのクラスの任意のメンバーを代表として選択できます。ただし、通常の代表は最小の正の剰余、つまりそのクラスに属する最小の非負の整数です（つまり、ユークリッド除算の余り）。^{[2]ただし、他の規則も可能です。コンピュータと計算機には、数値を保存および表現するさまざまな方法があるため、モジュロ演算の定義は}プログラミング言語または基礎となるハードウェアによって異なります。

ほぼすべてのコンピューティング システムでは、 aをnで割った商qと余りrは次の条件を満たします。

この場合も、剰余がゼロでない場合は符号の曖昧さが残ります。剰余には 2 つの選択肢があり、一方は負で他方は正です。この選択によって、連続する 2 つの商のうちどちらを使用して式 (1) を満たす必要があるかが決まります。整数論では正の剰余が常に選択されますが、コンピューティングでは、プログラミング言語は言語とaまたはnの符号に応じて選択します。^[a]たとえば、標準のPascalおよびALGOL 68では、負の除数に対しても正の剰余 (または 0) が返され、C90 などの一部のプログラミング言語では、nまたはaのいずれかが負の場合に実装に任せます (詳細については § プログラミング言語での表を参照)。 0 を法とするaはほとんどのシステムで未定義ですが、一部のシステムではaとして定義されています。

被除数と除数が両方とも正の場合、切り捨て、切り捨て、およびユークリッドの定義は一致します。被除数が正で除数が負の場合、切り捨てとユークリッドの定義は一致します。被除数が負で除数が正の場合、切り捨てとユークリッドの定義は一致します。被除数が負で除数が正の場合、切り捨てとユークリッドの定義は一致します。被除数と除数が両方とも負の場合、切り捨てと切り捨ての定義は一致します。

ライエン氏が述べたように、

ブーテは、ユークリッド除算は規則性と有用な数学的特性の点で他の除算よりも優れていると主張しているが、クヌースが提唱する切り捨て除算も優れた定義である。広く使用されているにもかかわらず、切り捨て除算は他の定義よりも劣っていることがわかっている。

— ダーン・ライジェン『コンピュータ科学者のための除算と剰余』^[5]

しかし、切り捨て除算は恒等式を満たす。^[6]${\displaystyle ({-a})/b={-(a/b)}=a/({-b})}$

一部の計算機にはmod()関数ボタンがあり、多くのプログラミング言語には、たとえばmod( a , n )と表現される同様の関数があります。また、またはのように、剰余演算子として「%」、「mod」、または「Mod」を使用する式をサポートするものもあります。 a % na mod n

同様の機能がない環境では、上記の 3 つの定義のいずれかを使用できます。

モジュロ演算の結果に被除数の符号（切り捨て定義）が含まれる場合、予期しない間違いが発生する可能性があります。

たとえば、整数が奇数かどうかをテストするには、2 による余りが 1 に等しいかどうかをテストする傾向があります。

bool is_odd ( int n ) {戻り値n % 2 == 1 ; }   
         

しかし、モジュロが被除数の符号を持つ言語では、これは誤りです。なぜなら、n (被除数) が負で奇数の場合、n mod 2 は -1 を返し、関数は false を返すからです。

正しい代替案の 1 つは、余りが 0 でないことをテストすることです (余り 0 は符号に関係なく同じであるため)。

bool is_odd ( int n ) {戻り値n % 2 != 0 ; }   
         

モジュロ演算は、剰余のある除算が毎回計算されるように実装される場合があります。特殊なケースでは、一部のハードウェアでは、より高速な代替手段が存在します。たとえば、2 の累乗のモジュロは、ビット単位のAND 演算として表現することもできます( x が正の整数であると仮定するか、切り捨てのない定義を使用します)。

x % 2n == x & (2n - 1)

例:

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

モジュロよりも効率的にビット演算を実装するデバイスやソフトウェアでは、これらの代替形式により計算が高速化される可能性があります。^[7]

コンパイラの最適化では、が 2 の累乗expression % constantである形式の式を認識し、 として自動的に実装することで、プログラマがパフォーマンスを犠牲にすることなく、より明確なコードを記述できるようにします。この単純な最適化は、被除数が符号なし整数型でない限り、モジュロ演算の結果に被除数の符号が含まれる言語 ( Cを含む) では不可能です。これは、被除数が負の場合、モジュロは負になるのに対し、は常に正になるためです。これらの言語では、代わりにビット単位の OR、NOT、AND 演算を使用して表現される等価性を使用する必要があります。 constantexpression & (constant-1)expression & (constant-1)x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)

定数除数最適化を使用して最初に除算を計算することによって、一般的な定数係数演算の最適化も存在します。

一部のモジュロ演算は、他の数学演算と同様に因数分解または展開できます。これは、 Diffie-Hellman 鍵交換などの暗号化証明で役立ちます。乗算、除算、累乗を含むプロパティでは、通常、aとnが整数である必要があります。

• 身元：
  • ( a mod n ) mod n = a mod n です。
  • xのすべての正の整数値に対して、 n ^x mod n = 0 です。
  • p がbの約数でない素数の場合、フェルマーの小定理より、ab ^{p −1} mod p = a mod pとなります。
• 逆:
  • [(− a mod n ) + ( a mod n )] mod n = 0。
  • b ⁻¹ mod n はモジュラー逆乗法を表します。これは、 bとnが互いに素である場合にのみ 定義され、左辺が[( b ⁻¹ mod n )( b mod n )] mod n = 1と定義されている場合です。
• 分配法:
  • ( a + b ) mod n = [( a mod n ) + ( b mod n )] mod n。
  • ab mod n = [( a mod n )( b mod n )] mod n。
• 部門（定義）: ⁠1つの/b⁠ mod n = [( a mod n )( b ⁻¹ mod n )] mod n、右辺が定義されている場合（つまり、 bとnが互いに素である場合）、それ以外の場合は未定義です。
• 逆乗算: [( ab mod n )( b ⁻¹ mod n )] mod n = a mod n。

さらに、多くのコンピュータ システムではdivmod、商と余りを同時に生成する機能が提供されています。例としては、x86 アーキテクチャのIDIV命令、C プログラミング言語のdiv()関数、Pythonのdivmod()関数などがあります。

場合によっては、 n を法とした演算の結果が0 とn − 1 の間ではなく、ある数値dとd + n − 1の間にあると便利なことがあります。その場合、d はオフセットと呼ばれ、d = 1が特に一般的です。

この演算には標準的な表記法がないようですので、とりあえずa mod _d nを使用します。したがって、次の定義が得られます。^[57] d ≤ x ≤ d + n − 1かつx mod n = a mod nの場合、x = a mod _d n。明らかに、通常のモジュロ演算はゼロオフセットに対応します：a mod n = a mod ₀ n。

オフセットによる剰余演算は、次のようにfloor 関数と関連しています。

${\displaystyle a\operatorname {mod} _{d}n=an\left\lfloor {\frac {ad}{n}}\right\rfloor .}$

これを確かめるために、 とします。まず、x mod n = a mod nであることを示します。一般に、すべての整数bに対して( a + bn ) mod n = a mod nは真です。したがって、 の特定のケースでもこれは真ですが、これは であることを意味し、これが証明したかったことです。d ≤ x ≤ d + n − 1であることがまだ証明されていません。kおよびrを、 0 ≤ r ≤ n − 1でa − d = kn + rとなる整数とします(ユークリッドの除算を参照)。すると となり、したがって となります。ここで0 ≤ r ≤ n − 1を取り、両辺にd を加えると、 ≤ d + r ≤ d + n − 1が得られます。しかし、 x = d + rであることはすでに確認したので、これで終わりです。 ${\textstyle x=an\left\lfloor {\frac {ad}{n}}\right\rfloor }$${\textstyle b=-\!\left\lfloor {\frac {ad}{n}}\right\rfloor }$${\textstyle x{\bmod {n}}=\left(an\left\lfloor {\frac {ad}{n}}\right\rfloor \right)\!{\bmod {n}}=a{\bmod {n}}}$${\textstyle \left\lfloor {\frac {ad}{n}}\right\rfloor =k}$${\textstyle x=an\left\lfloor {\frac {ad}{n}}\right\rfloor =a-nk=d+r}$

オフセットa mod _d nの法はMathematicaでは次のように実装されていますMod[a, n, d] 。^[57]

クヌースの床割り算とユークリッド割り算は数学的に優雅であるにもかかわらず、プログラミング言語では一般に切り捨て割り算に基づく剰余がはるかに一般的です。ライエンは切り捨て整数割り算を与えられた2つの割り算を計算するための次のアルゴリズムを提供しています: ^[5]

/* C の ldiv() スタイルのユークリッドおよび Floored divmod */ 
typedef struct { /* この構造体は C stdlib.h の一部ですが、わかりやすくするためにここで再現されています */ long int quot ; long int rem ; } ldiv_t ;  
  
    
    
 

/* ユークリッド除算 */ 
inline ldiv_t ldivE ( long numer , long denom ) { /* C99 および C++11 言語では、これら両方を切り捨てとして定義します。 */ long q = numer / denom ; long r = numer % denom ; if ( r < 0 ) { if ( denom > 0 ) { q = q - 1 ; r = r + denom ; } else { q = q + 1 ; r = r - denom ; } } return ( ldiv_t ){. quot = q , . rem = r }; }      
  
       
       
      
        
          
          
      
          
          
    
  
        


/* 切り捨て除算 */ 
inline ldiv_t ldivF ( long numer , long denom ) { long q = numer / denom ; long r = numer % denom ; if (( r > 0 && denom < 0 ) || ( r < 0 && denom > 0 )) { q = q - 1 ; r = r + denom ; } return ( ldiv_t ){. quot = q , . rem = r }; }      
       
       
                  
        
        
  
        

どちらの場合も、剰余は商とは独立して計算できますが、その逆はできません。論理分岐は同じなので、ここでは画面スペースを節約するために演算が結合されています。

• モジュロ (曖昧さ回避) –モジュロという単語はさまざまな用途で使われていますが、そのすべては1801 年にカール F. ガウスがモジュラー演算を導入したことに由来しています。
• モジュロ (数学)、数学における用語の一般的な使用法
• モジュラー指数
• 回転（角度）

• さまざまな種類の整数除算
• Modulorama、掛け算表の循環表現のアニメーション（フランス語での説明）