モジュラー乗法逆元

mを法とする合同関係は、整数の集合をm個の合同クラスに分割します。これらのm個の対象に対して、加算と乗算の演算は次のように定義できます。2 つの合同クラスを加算または乗算するには、まず各クラスから代表元を (任意の方法で) 選び、次にその 2 つの代表元に対して通常の整数演算を実行し、最後に整数演算の結果が属する合同クラスを、合同クラスに対する演算の結果として取ります。記号で表すと、これらの定義は次のようになります。

${\displaystyle {\overline {a}}+{\overline {b}}={\overline {a+b}}}$

そして

${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {ab}},}$

どこ${\displaystyle +}$そして${\displaystyle \,\!\cdot }$左側の記号は、mを法とする合同類の加算と乗算を表します。これらの演算は明確に定義されており、最終結果は結果を得るために選択された代表値に依存しません。

これら2つの定義された演算を持つm個の合同類は、 mを法とする整数環と呼ばれる可換環を形成する。これらの代数的対象にはいくつかの表記法が用いられており、最もよく用いられるのは${\displaystyle \mathbb {Z} /m\mathbb {Z} }$または${\displaystyle \mathbb {Z} /m}$しかし、いくつかの初歩的なテキストや応用分野では、簡略化された表記法が使用されています。${\displaystyle \mathbb {Z} _{m}}$他の代数的対象との混同が起こりにくい場合。

mを法とする整数の合同類は、伝統的にm を法とする剰余類として知られており、これは合同類のすべての要素がmで割ったときに同じ剰余（つまり「剰余」）を持つという事実を反映しています。それぞれが異なるm を法とする合同類から選ばれるように選択された m 個の整数の集合は、 mを法とする剰余の完全系と呼ばれます。^{[ 9 ]}除算アルゴリズムは、整数の集合{0, 1, 2, ..., m − 1}がmを法とする剰余の完全系を形成し、mを法とする最小剰余系として知られていることを示しています。算術問題を扱う際には、剰余の完全系を扱い、合同の言語を使用する方が便利な場合もあれば、環の合同類の観点から考える方が便利な場合もあります。${\displaystyle \mathbb {Z} /m\mathbb {Z} }$の方がより有用である。^{[ 10 ]}

mを法とする完全剰余系のすべての要素が法乗法逆元を持つわけではありません。たとえば、m > 1の場合、0 は法乗法逆元を持ちません。m と互いに素でない要素を完全剰余系から取り除いた後に残るものを簡約剰余系と呼び、そのすべての要素が法乗法逆元を持ちます。簡約剰余系の要素の数は${\displaystyle \phi (m)}$、 どこ${\displaystyle \phi }$はオイラーのトーシェント関数、つまりmより小さい正の整数のうち、 mと互いに素な整数の数です。

単位元を持つ一般環では、すべての要素が乗法逆元を持つわけではなく、乗法逆元を持つ要素は単位元と呼ばれます。2 つの単位元の積は単位元であるため、環の単位元は群を形成し、環の単位元群と呼ばれ、 R が環の名前である場合はR ^×と表記されることがよくあります。m を法とする整数環の単位元群は、 mを法とする整数の乗法群と呼ばれ、既約剰余系と同型です。特に、位数(サイズ)を持ち、${\displaystyle \phi (m)}$。

mが素数、例えばpである場合、${\displaystyle \phi (p)=p-1}$そして、すべての非ゼロ要素${\displaystyle \mathbb {Z} /p\mathbb {Z} }$乗法逆元を持つので、${\displaystyle \mathbb {Z} /p\mathbb {Z} }$は有限体である。この場合、pを法とする整数の乗法群は位数p − 1の巡回群を形成する。

mを法とするaのモジュラー乗法逆元は、拡張ユークリッドアルゴリズムを用いて求めることができる。

ユークリッドの互除法は、2 つの整数aとmの最大公約数 (gcd) を求めます。aが法mに関して乗法逆元を持つ場合、この gcd は 1 になります。この互除法によって生成されるいくつかの方程式のうち最後の方程式を解くと、この gcd を求めることができます。次に、「後退代入」と呼ばれる方法を使用して、元のパラメータとこの gcd を関連付ける式を得ることができます。言い換えれば、ベズーの恒等式を満たす整数xとyを見つけることができます。

${\displaystyle ax+my=\gcd(a,m)=1.}$

書き直した、これは

${\displaystyle ax-1=(-y)m,}$

つまり、

${\displaystyle ax\equiv 1{\pmod {m}},}$

つまり、 aのモジュラー乗法逆元が計算された。このアルゴリズムのより効率的なバージョンは拡張ユークリッドアルゴリズムであり、補助方程式を使用することで、アルゴリズムの 2 回の実行 (逆代入はアルゴリズムを逆方向に実行することと考えることができる) を 1 回に減らす。ビッグ O 記法では、このアルゴリズムは、 | a | < mを仮定してO(log ² ( m ))の時間で実行され、非常に高速で、一般的に代替手段であるべき乗よりも効率的であると考えられている。

例えば、モジュラー乗法逆元は${\displaystyle a=15}$弾性率に関して${\displaystyle m=34}$は${\displaystyle -9}$だけでなく、${\displaystyle -9+34=25,}$つまり、リングの中で${\displaystyle \mathbb {Z} /34\mathbb {Z} ,}$残基クラス${\displaystyle {\overline {15}}}$逆関数と可逆である

${\displaystyle {\overline {15}}^{\!\ -1}={\overline {-9}}={\overline {25}}.}$

なぜなら

${\displaystyle g=\mathrm {gcd} (m,a)=1=4m-9a,}$

隣接する計算によると。最初のステップでは、ユークリッド除算に対応して「${\displaystyle \;\!34\div 15}$は${\displaystyle 2}$余りあり${\displaystyle 4\!\ }$「、${\displaystyle -2}$方程式${\displaystyle 15=0m+1a}$方程式に追加されます${\displaystyle 34=1m+0a}$これは、${\displaystyle 4=1m-2a.}$左側の残余が${\displaystyle 0,}$${\displaystyle g}$その上に立つ（または一般的に）${\displaystyle \pm g}$（負の剰余も許容される場合）。対応する右端の表では、同様の行操作で、明らかに省略できる。${\displaystyle m}$-列。最後に、${\displaystyle {\overline {15}}{}^{\!\ -1}={\overline {-9}}}$直接確認できます：

${\displaystyle {\overline {15}}\cdot {\overline {-9}}={\overline {-135}}={\overline {-135+4\cdot 34}}={\overline {1}}}$

で${\displaystyle \mathbb {Z} /34\mathbb {Z} .}$

拡張ユークリッドアルゴリズムの代替として、オイラーの定理を使用してモジュラー逆数を計算することができます。^{[ 11 ]}

オイラーの定理によれば、a がmと互いに素である場合、つまりgcd( a , m ) = 1ならば、

${\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}$

どこ${\displaystyle \phi }$はオイラーのトーシェント関数である。これは、 a が乗法群に属するという事実から導かれる。${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$^×は、 a がmと互いに素である場合に限り 成り立つ。したがって、モジュラー乗法逆元は直接求めることができる。

${\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}$

mが素数である特別な場合、${\displaystyle \phi (m)=m-1}$そしてモジュラー逆元は次のように与えられる。

${\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}$

この方法は一般的に拡張ユークリッドアルゴリズムよりも遅いですが、モジュラべき乗の実装が既に利用可能な場合に使用されることがあります。この方法の欠点としては、以下のようなものがあります。

• 価値${\displaystyle \phi (m)}$は既知である必要があり、最も効率的な既知の計算にはmの因数分解が必要です。因数分解は計算上困難な問題であると広く考えられています。しかし、 を計算することは${\displaystyle \phi (m)}$mの素因数分解が分かっている場合は、これは簡単です。
• べき乗の相対的なコスト。モジュラーべき乗を使用すればより効率的に実装できますが、 mの値が大きい場合は、モンゴメリー還元法が最も効率的に計算できます。この方法自体が、そもそも計算すべきであったモジュラー逆元 mod mを必要とします。モンゴメリー法を使用しない場合、各ステップでmod mによる除算が必要となる標準的な二進べき乗は、 mが大きい場合に処理速度が遅くなります。

この手法の注目すべき利点の1つは、 aの値に依存する条件分岐が存在しないため、公開鍵暗号において重要な秘密情報となる可能性のあるaの値をサイドチャネル攻撃から保護できることです。このため、 Curve25519の標準実装では、逆行列を計算するためにこの手法が用いられています。

複数の数a _iの逆数を共通のmで割った値を、ユークリッドアルゴリズムを 1 回呼び出し、追加の入力ごとに 3 回の乗算を行うことで計算することが可能です。^{[ 12 ]}基本的な考え方は、すべてのa _i の積を作り、それを反転し、次にすべてのj ≠ iに対してa _{jを掛けて、目的の}a ⁻¹ _iだけを残すことです。

より具体的には、アルゴリズムは（すべての算術演算はmを法として実行される）：

1. 接頭辞積を計算する${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$すべてのi ≤ nに対して。
2. 利用可能な任意のアルゴリズムを用いて、b ⁻¹ _nを計算してください。
3. iがnから2 までの 場合、計算します。
   • a ⁻¹ _i = b ⁻¹ _i b _{i −1}および
   • b ⁻¹ _{i −1} = b ⁻¹ _i a _i。
4. 最後に、a ⁻¹ ₁ = b ⁻¹ ₁となります。

並列コンピューティングを活用するために、乗算を線形ではなくツリー構造で実行することが可能です。

モジュラスMが次の形式の場合${\displaystyle p^{m}}$ある素数pと正の整数mに対して、ニュートン・ラフソン反復法を用いることでモジュラー乗法逆元を効率的に計算することが可能であり、逆元は次のように計算できる。${\displaystyle O(\log m)}$乗算。次のことが示せる。

${\displaystyle ax\equiv 1{\pmod {p^{k}}}}$

（つまり、xはある素数のべき乗を法とするaのモジュラー乗法逆元である）${\displaystyle p^{k}}$）、 それから

${\displaystyle ax\left(2-ax\right)\equiv 1{\pmod {p^{2k}}}}$

つまり、まず素数pまたはその小さなべき乗を法とするaのモジュラー乗法逆数を計算し、次にニュートン・ラフソン法を繰り返して、より大きな素数のべき乗を法とする逆数を計算することで、モジュラー逆数計算を実行できるということである。${\displaystyle p^{2^{n}*k}}$nの値が徐々に大きくなるにつれて。^{[ 13 ] [ 14 ]}

この方法の実用的な用途は、2 のべき乗を法とするモジュラー乗法逆数を効率的に計算することです。このような計算を行うには、すべての奇数が 2 のべき乗を法とする自身のモジュラー乗法逆数であることに注目することから始めることができます。${\displaystyle 2^{3}}$検査によって明らかになるように：

${\displaystyle 1*1=1\equiv 1{\pmod {8}}}$、${\displaystyle 3*3=9\equiv 1{\pmod {8}}}$、${\displaystyle 5*5=25\equiv 1{\pmod {8}}}$、${\displaystyle 7*7=49\equiv 1{\pmod {8}}}$、

そして、ニュートン・ラフソン反復法を繰り返し用いて、モジュラー逆数をモジュラーで計算する。${\displaystyle 2^{6}}$、${\displaystyle 2^{12}}$、${\displaystyle 2^{24}}$等々。

例えば、C プログラミング言語では、uint64_tデータ型に対する加算、減算、乗算はすべて剰余演算で行われます。${\displaystyle 2^{64}}$奇数aの法乗法逆元を計算することができます。${\displaystyle 2^{64}}$ニュートン・ラフソン法を5回反復する以下の関数を使用します。

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { uint64_t x = a ; for ( int i = 0 ; i < 5 ; i ++ ) x *= 2 - a * x ; return x ; }

アプリケーションやプラットフォームによっては、このルーチンをさらに最適化することが理にかなっている場合があります。たとえば、ルックアップ テーブルを使用して、より大きな 2 のべき乗を法とする逆数を提供することで、最初の数回の反復をスキップできます。また、一部のシステムでは、32 ビット乗算が 64 ビット乗算よりも高速な場合があり、その場合は、逆数が法となるまで 32 ビット乗算のみを使用することで、ある程度の高速化が得られます。${\displaystyle 2^{32}}$が取得された後、64 ビット乗算に切り替えます。このような最適化を適用すると、モジュラ乗法逆元を計算する C ルーチンは、${\displaystyle 2^{64}}$になる:

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { static const uint8_t tbl [ 256 ] = { 0 , 1 , 0 , 171 , 0 , 205 , 0 , 183 , 0 , 57 , 0 , 163 , 0 , 197 , 0 , 239 , 0 , 241 , 0 , 27 , 0 , 61 , 0 , 167 , 0 , 41 , 0 , 19 , 0 , 53 , 0 , 223 , 0 , 225 , 0 , 139 , 0 , 173 , 0 , 151 , 0 , 25 , 0 , 131 , 0 , 165 , 0 , 207 , 0 , 209 , 0 , 251 , 0 , 29 , 0 , 135 , 0 , 9 , 0 , 243 , 0 , 21 , 0 , 191 , 0 , 193 , 0 , 107 , 0 , 141 , 0 , 119 , 0 , 249 , 0 , 99 , 0 , 133 , 0 , 175 , 0 , 177 , 0 , 219 , 0 , 253 , 0 , 103 , 0 , 233 , 0 、211、0 、​​245、0、159、0、161、0、75、0、109、0、87、0、217、0、67、0、101、0、143、0、145、0、187、0、221、0、71、0、201、0、179、0、213、0、127、0、129、0、43、0、77、0、55、0、185、0、35、0、69、0、111​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ , 0 , 113 , 0 , 155 , 0 , 189 , 0 , 39 , 0 , 169 , 0 , 147 , 0 , 181 , 0 , 95 , 0 , 97 , 0 , 11 , 0 , 45 , 0 , 23 , 0 , 153 , 0 , 3 , 0 , 37 , 0 , 79 , 0 , 81 , 0 , 123 , 0 , 157 , 0 , 7 , 0 , 137 , 0 , 115 , 0 , 149 , 0 , 63 , 0 , 65 , 0 , 235 、0 、13 , 0 , 247 , 0 , 121 , 0 , 227 , 0 , 5 , 0 , 47 , 0 , 49 , 0 , 91 , 0 , 125 , 0 , 231 , 0 , 105 , 0 , 83 , 0 , 117 , 0 , 31 , 0 , 33 , 0 , 203 , 0 , 237 , 0 , 215 , 0 , 89 , 0 , 195 , 0 , 229 , 0 , 15 , 0 , 17 , 0 , 59 , 0 , 93 , 0 , 199 , 0 , 73 , 0 , 51 , 0 , 85 , 0 , 255 }; uint32_t a32 = ( uint32_t ) a ; uint32_t x = tbl [ a & 0xFF ]; // 2^8 を法とする逆数x *= 2 - a32 * x ; // 32 ビット乗算x *= 2 - a32 * x ; // 32 ビット乗算return x * ( 2 - a * x ); // 64 ビット乗算}