モジュラー逆乗法

数学、特に算数の分野において、整数aのモジュラー逆数とは、積axが法mに関して1と合同となる整数xのことである。^[1]モジュラー算術の標準表記では、この合同は次のように書かれる。

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

これは、m が量ax − 1を（均等に）割り切る、または別の言い方をすると、 ax を整数mで割った余りが1 であるというステートメントの簡潔な書き方です。 a がm を法として逆数を持つ場合、この合同の解は無限にあり、この法に関して合同類を形成します。さらに、 aと合同な任意の整数（つまり、aの合同類）には、モジュラ乗法逆数としてxの合同類の任意の要素があります。 w を含む合同類を示すためにの表記法を使用すると、これは、合同類のモジュロ乗法逆数が次の 合同類であると表現できます。${\displaystyle {\overline {w}}}$${\displaystyle {\overline {a}}}$${\displaystyle {\overline {x}}}$

${\displaystyle {\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},}$

ここで、記号はmを法とする同値類の乗算を表します。^{[2]このように記述すると、}有理数または実数の集合における乗法逆数 の通常の概念との類似性が、数を合同類に置き換え、2項演算を適切に変更することで明確に表現されます。 ${\displaystyle \cdot_{m}}$

実数に対する類似の演算と同様に、この演算の基本的な用途は、可能な場合には、次の形式の線形合同を解くことである。

${\displaystyle ax\equiv b{\pmod {m}}.}$

モジュラー逆数を見つけることは、公開鍵暗号やRSAアルゴリズムなどの暗号分野でも実用的な応用があります。^{[3] [4] [5]}これらのアプリケーションをコンピュータで実装する利点は、モジュラー逆数の計算に使用できる 非常に高速なアルゴリズム（拡張ユークリッドの互除法）が存在することです。

与えられた正の整数mに対して、2つの整数aとb の差がm で割り切れる場合、これらの整数はm を法として合同であると言われる。この2項関係は次のように表される。

${\displaystyle a\equiv b{\pmod {m}}.}$

これは整数の集合 上の同値関係であり、同値類はmを法とする合同類またはmを法とする剰余類と呼ばれる。整数aを含む合同類を とすると 、^[6]${\displaystyle \mathbb {Z} }$${\displaystyle {\overline {a}}}$

${\displaystyle {\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.}$

線型合同は、次の形式のモジュラー合同である。

${\displaystyle ax\equiv b{\pmod {m}}.}$

実数上の線形方程式とは異なり、線形合同式には 0 個、1 個、または複数の解があります。xが線形合同式の解である場合、その中のすべての要素も解です。したがって、線形合同式の解の数について話すときは、解を含む異なる合同クラスの数について言及しています。 ${\displaystyle {\overline {x}}}$

dがaとmの最大公約数である場合、線型合同式ax ≡ b (mod m )は、 dがbを割り切る場合にのみ解を持つ。dがbを割り切る場合、解は正確にd個存在する。^[7]

整数aの係数mに関するモジュラー逆数は線形合同の解である。

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

前の結果は、解が存在するのはgcd( a , m ) = 1の場合のみ、つまりaとm が互いに素（すなわち互いに素）であるときのみであることを示しています。さらに、この条件が成立する場合、解は正確に1つ存在し、つまり解が存在する場合、モジュラー逆元は一意です。^[8] bとb' が両方とも a のモジュラー逆元である場合、

${\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}$

したがって

${\displaystyle a(b-b')\equiv 0{\pmod {m}}.}$

a ≡ 0 (mod m )の場合、gcd( a , m ) = mとなり、aにはモジュラー逆数さえ存在しません。したがって、b ≡ b' (mod m )となります。

ax ≡ 1 (mod m )に解がある 場合、次のように表記されることが多い。

${\displaystyle x\equiv a^{-1}{\pmod {m}},}$

しかし、これは表記法の乱用であると考えられます。なぜなら、の逆数と誤解される可能性があるからです(これは、モジュラー逆数とは対照的に、aが 1 または -1 の場合を除いて整数ではありません) 。 合同類の逆数は、次のセクションで定義される乗法を持つ合同類であるため、 a が合同類を表すトークンとして解釈される場合、表記法は適切です。${\displaystyle a}$${\displaystyle {\overline {a}}}$

mを法とする合同関係は、整数の集合をm個の合同類に分割する。これらのm個のオブジェクトに対する加算と乗算の演算は、次のように定義できる。2 つの合同類を加算または乗算するには、まず各類から代表を (任意の方法で) 選び、次に 2 つの代表に対して整数の通常の演算を実行し、最後に整数演算の結果が含まれる合同類を合同類に対する演算の結果として取る。合同類に対する演算を表す記号、およびでは、これらの定義は次のようになる。 ${\displaystyle +_{m}}$${\displaystyle \cdot _{m}}$

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

そして

${\displaystyle {\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.}$

これらの操作は明確に定義されているため、最終結果は、結果を得るために行われた代表者の選択に依存しません。

これら 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 を法とする最小剰余系として知られる。算術問題を扱う場合、剰余の完全系を扱い、合同の言語を使用する方が便利な場合もあれば、環の合同類の観点の方が便利な場合もある。^[10]${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

mを法とする完全剰余系のすべての元がモジュラー逆数を持つわけではありません。たとえば、ゼロには決してありません。mと互いに素でない完全剰余系の元を取り除いた後に残ったものは、すべての元がモジュラー逆数を持つ、縮小剰余系と呼ばれます。縮小剰余系の元の数は で、 はオイラーのトーシェント関数、つまりmと互いに素であるm未満の正の整数の数です。 ${\displaystyle \phi (m)}$${\displaystyle \phi }$

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

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

任意の整数 に対して、 は常にを法とするのモジュラー逆乗法です。 なぜなら だからです。 例としては、、などがあります。 ${\displaystyle n>1}$${\displaystyle n^{2}-n+1}$${\displaystyle n+1}$${\displaystyle n^{2}}$${\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}$${\displaystyle 3\times 3\equiv 1{\pmod {4}}}$${\displaystyle 4\times 7\equiv 1{\pmod {9}}}$${\displaystyle 5\times 13\equiv 1{\pmod {16}}}$

次の例では10を法として用いている。2つの整数が10を法として合同となるのは、その差が10で割り切れる場合のみである。例えば、

${\displaystyle 32\equiv 2{\pmod {10}}}$10は32−2=30を割り切るので、

${\displaystyle 111\equiv 1{\pmod {10}}}$10 は 111 − 1 = 110 を割り切るからです。

この係数に関する 10 個の合同クラスの一部は次のとおりです。

${\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}}$

${\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \}}$

${\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}}$そして

${\displaystyle {\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.}$

線形合同4 x ≡ 5 (mod 10)には解がありません。5 に合同な整数 (つまり、 内の整数) はすべて奇数であるのに対し、 4 x は常に偶数だからです。ただし、線形合同4 x ≡ 6 (mod 10)には 2 つの解、つまりx = 4とx = 9があります。gcd (4, 10) = 2 であり、2 は 5 を割り切れませんが、6 を割り切れます。 ${\displaystyle {\overline {5}}}$

gcd(3, 10) = 1なので、線形合同3 x ≡ 1 (mod 10)には解が存在する、つまり 3 を法として 10 を法とするモジュラー逆数が存在する。実際、7 はこの合同を満たす (つまり、21 − 1 = 20)。しかし、他の整数もこの合同を満たす。たとえば、17 と −3 (つまり、3(17) − 1 = 50 と 3(−3) − 1 = −10)。特に、 のすべての整数は、これらの整数が何らかの整数rに対して7 + 10 rという形式を持つため、 この合同を満たす。${\displaystyle {\overline {7}}}$

${\displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}$

は 10 で割り切れます。この合同には、この合同クラスの解しかありません。この場合の解は、すべての可能なケースをチェックすることで得られますが、より大きな係数には体系的なアルゴリズムが必要になります。これは次のセクションで説明します。

合同類 と の積は、の元、たとえば 25 と の元、たとえば −2 を選択し、それらの積 (25)(−2) = −50 が合同類 にあることを観察することによって得られます。したがって、 です。加算も同様の方法で定義されます。10 個の合同類と、合同類の加算と乗算のこれらの演算により、10 を法とする整数の環、つまり が形成されます。 ${\displaystyle {\overline {5}}}$${\displaystyle {\overline {8}}}$${\displaystyle {\overline {5}}}$${\displaystyle {\overline {8}}}$${\displaystyle {\overline {0}}}$${\displaystyle {\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}}$${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

10 を法とする完全な剰余系は、各整数が 10 を法とする異なる合同類に属する集合 {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} となる。10 を法とする唯一の最小剰余系は {0, 1, 2, ..., 9} である。10 を法とする簡約剰余系は {1, 3, 7, 9} となる。これらの数で表される任意の 2 つの合同類の積も、これら 4 つの合同類のいずれかである。これは、これら 4 つの合同類がグループ (この場合は、3 または 7 を (乗法) 生成元として持つ、位数 4 の巡回群) を形成することを意味する。表される合同類は、環 の単位群を形成する。これらの合同類は、モジュラー乗法逆数を持つものとまったく同じである。 ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Wikibookアルゴリズム実装には、拡張ユークリッドアルゴリズムに関するページがあります。

拡張ユークリッドの互除法を使用して、 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 ))の時間で実行され、非常に高速で、一般に代替の累乗法よりも効率的であると考えられています。

拡張ユークリッドの互除法の代替として、オイラーの定理はモジュラー逆を計算するために使われることがある。^[11]

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

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

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

${\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}}.}$

この方法は一般に拡張ユークリッド互除法よりも低速ですが、モジュラー指数の実装がすでに利用可能な場合に使用されることがあります。この方法の欠点は次のとおりです。

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

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

ユークリッド互除法を1回呼び出し、追加入力ごとに3回の乗算を行うことで、複数の数a _iの逆数を共通のmを法として計算することができます。 ^{[12]基本的な考え方は、すべての}a _i の積を作成し、それを反転し、すべてのj ≠ iに対してa _jを乗じて、必要なaのみを残すことです。⁻¹
_私。

より具体的には、アルゴリズムは次のようになります（すべての演算はm を法として実行されます）。

1. すべてのi ≤ nのプレフィックス積 を計算します。${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$
2. 計算b⁻¹
   _個利用可能なアルゴリズムを使用します。
3. iがnから2まで の場合、計算する
   • 1つの⁻¹
     _私=ば⁻¹
     _私b _{i −1}と
   • b⁻¹
     _私−1=ば⁻¹
     _私私_は。
4. 最後に、⁻¹
   ₁=ば⁻¹
   ₁。

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

モジュラー逆数を見つけることは、モジュラー算術の理論に依存するアルゴリズムで多くの用途があります。たとえば、暗号化では、モジュラー算術を使用すると、一部の操作をより高速かつ少ないストレージ要件で実行できますが、他の操作はより困難になります。^[13]これらの機能は両方とも有利に使用できます。特に、RSAアルゴリズムでは、慎重に選択されたモジュラスに関して逆数である2つの数値を使用してメッセージの暗号化と復号化が行われます。これらの数値の1つは公開され、迅速な暗号化手順で使用できますが、復号化手順で使用されるもう1つは隠されたままになります。公開された数値から隠された数値を決定することは計算上不可能であると考えられており、これがシステムがプライバシーを確​​保するために機能する理由です。^[14]

別のコンテキストでの別の例として、コンピュータ サイエンスにおける正確な除算の問題を考えてみましょう。この問題では、それぞれがkで割り切れる奇数ワード サイズの数値のリストがあり、それらすべてをkで割りたいとします。1 つの解決策は次のとおりです。

1. 拡張ユークリッドの互除法を使用して、k mod 2 ^wのモジュラー逆数であるk ⁻¹を計算します。ここで、w はワード内のビット数です。数値が奇数であり、モジュラスに奇因数がないため、この逆数が存在します。
2. リスト内の各数値をk ⁻¹倍し、結果の最下位のワードを取ります。

多くのマシン、特に除算のハードウェア サポートがないマシンでは、除算は乗算よりも遅い演算であるため、このアプローチにより大幅な高速化が実現できます。最初のステップは比較的遅いですが、実行する必要があるのは 1 回だけです。

モジュラー逆乗法は、中国剰余定理によって保証される線形合同系の解を得るために使用されます。

例えば、システム

X ≡ 4 (mod 5)

X ≡ 4 (7 を法として)

X ≡ 6 (11を法として)

5、7、11は互いに素なので、共通の解があります。解は次のように与えられます。

X = t ₁ (7 × 11) × 4 + t ₂ (5 × 11) × 4 + t ₃ (5 × 7) × 6

どこ

t ₁ = 3 は 7 × 11 (mod 5) のモジュラー逆数です。

t ₂ = 6は5 × 11（mod 7）のモジュラー逆数であり、

t ₃ = 6 は 5 × 7 (mod 11) のモジュラー逆数です。

したがって、

X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

そしてその独特な短縮形で

X ≡ 3504 ≡ 39 (mod 385)

385 は5、7、11 の 最小公倍数だからです。

また、モジュラー逆数は、クロスターマン和の定義において重要な役割を果たします。

• 逆合同型生成器- モジュラー乗法逆数を使用する疑似乱数生成器
• 合理的な再構成（数学）

• アイルランド、ケネス、ローゼン、マイケル（1990）、現代数論への古典的入門（第2版）、シュプリンガー・フェアラーク、ISBN 0-387-97329-X
• ローゼン、ケネス H. (1993)、初等数論とその応用(第 3 版)、Addison-Wesley、ISBN 978-0-201-57889-8
• シューマッハー、キャロル(1996)。第 0 章: 抽象数学の基本概念。Addison- Wesley。ISBN 0-201-82653-4。
• トラップ、ウェイド; ワシントン、ローレンス C. (2006)、暗号理論入門(第 2 版)、Prentice-Hall、ISBN 978-0-13-186239-5

• ワイスタイン、エリック・W.「モジュラー・インバース」。マスワールド。
• Guevara Vasquez, Fernando は、ユークリッドのアルゴリズムを使用してモジュロ乗法逆数を解く例を示しています。