モジュラ逆数のソースを表示

{{Expand English|date=2022-02-15}}
{{Refimprove|date=March 2007}}
[[合同算術]]において、[[整数の合同#法_n_に関する合同|法]] {{Math|''m'' > 1}} に関する[[整数]] {{Mvar|a}} の'''モジュラ逆数'''（モジュラぎゃくすう、{{lang-en-short|''modular multiplicative inverse''}}）とは,

:<math>ax \equiv xa \equiv 1 \pmod{m}</math>
という関係にある整数 {{Mvar|x}} の属する合同類（あるいはその標準的な代表元）のことで、これを {{Math|''a''{{sup|&minus;1}}}} で表す。これは、整数の法 {{Mvar|m}} に関する[[剰余類環|合同類環]] <math>\mathbb{Z}/m\mathbb{Z}</math> における[[乗法逆元]]である。ある種の応用においては、モジュラ逆数 {{Math|''a''{{sup|&minus;1}}}} が <math>\mathbb{Z}/m\mathbb{Z}</math> に属さないような場合を考えることもある。

{{Mvar|a}} の {{Mvar|m}} を法とする逆数が存在するための[[必要十分条件]]は {{Mvar|a}} と {{Mvar|m}} とが[[互いに素 (整数論)|互いに素]]（即ち、[[最大公約数]] {{Math|gcd({{Mvar|a}}, {{Mvar|m}})}} が {{Math|1}}）となることである。法 {{Mvar|m}} に関する {{Mvar|a}} のモジュラ逆数が存在するならば、{{Mvar|m}} を法とした {{Mvar|a}} による[[除法]]（「[[ユークリッド除法|余り付き除法]]」ではない）を、モジュラ逆数を掛けることとして定義することができる。

== 例 ==
整数 {{Math|3}} の法 {{Math|11}} に関するモジュラ逆数 {{Mvar|x}} を求める。これは
:<math>3^{-1} \equiv x \pmod{11}</math>
を満たすものを計算するということだが、その意味は
:<math>3x \equiv 1 \pmod{11}</math>
なる ''x'' を求めることに他ならない。<math>\mathbb{Z}/11\mathbb{Z}</math> においてこの合同式の解 {{Mvar|x}} が {{Math|4 mod 11}} であることは
:<math>3 \times 4 = 12 \equiv 1 \pmod{11}</math>
から明らかであり、従って {{Math|11}} を法として {{Math|3}} の逆数は {{Math|4}} である。こうして <math>\mathbb{Z}/11\mathbb{Z}</math> において逆数が求まったが、上記の合同式を満たす {{Mvar|x}} は {{Math|4}} のみではない。残りの解は、得られた {{Math|4}} に {{Math|{{Mvar|m}}{{=}}11}} の倍数を加えたものとして得られる。一般にこの例において {{Mvar|x}} となり得る整数は
:<math>4 + 11 z, z \in \mathbb{Z}</math>
の形をしており、これは {{Math|{{mset|…, -18, -7, '''4''', 15, 26, …}}}} という集合を成す。

== 逆数計算 ==
=== 拡張ユークリッド互除法 ===
法 {{Mvar|m}} に関する {{Mvar|a}} のモジュラ逆数は、[[ユークリッドの互除法#拡張された互除法|拡張ユークリッド互除法]]を用いて計算することができる。互除法のアルゴリズムは[[ベズーの等式]]
:<math>ax + by = \gcd(a, b)</math>
の解を求めるものである。ただし、{{Math|''a'', ''b''}} が既知で、整数 {{Math|''x'', ''y''}} および {{Math|gcd(''a'', ''b'')}} がこのアルゴリズムから求まる。

さて、モジュラ逆数は合同式
:<math>ax \equiv 1 \pmod{m}</math>
の解であったから、合同式の定義により {{Math|''m'' {{!}} ''ax'' &minus; 1}}（{{Mvar|m}} は {{Math|''ax'' &minus; 1}} の[[約数]]）、即ち適当な整数 {{Mvar|q}} を用いて
:<math>ax - 1 = qm</math>
となる。これを整理した
:<math>ax - qm = 1</math>
は、{{Mvar|a}} と {{Mvar|m}} が既知で、逆数となる {{Mvar|x}} と捨てられる {{Mvar|q}} は未知であるから、拡張ユークリッド互除法が解く等式とまったく同じ形をしている。違う点といえば {{Math|1=gcd(''a'', ''m'') = 1}} が「求まる」のではなくて「所与」であること程度で、それゆえ {{Mvar|a}} が {{Mvar|m}} と互いに素でなければならず、さもなくば逆元 {{Mvar|x}} は存在しない。

このアルゴリズムの計算量は {{Math|{{mabs|''a''}} &lt; ''m''}} と仮定すると {{Math|''O''((log ''m''){{sup|2}})}} で、一般に冪乗の計算よりも効率的である。

=== オイラーの定理の利用 ===
拡張ユークリッド互除法の代わりにオイラーの定理をモジュラ逆数の計算に利用することもできる<ref>{{cite book
 |first=Thomas
 |last=Koshy
 |title=Elementary number theory with applications
 |edition=2nd
 |publisher=Academic Press
 |date=2007-05-22
 |isbn=978-0-12-372487-8
 |page=346
 |ref=harv
}}</ref>。

[[オイラーの定理_(数論)|オイラーの定理]]によれば、{{Mvar|a}} が {{Mvar|m}} と[[互いに素 (整数論)|互いに素]]ならば、[[オイラーのトーシェント函数|オイラー函数]] {{Math|''φ''(''m'')}} に対して
:<math>a^{\varphi(m)} \equiv 1 \pmod{m}</math>
が成り立つ。これは {{Mvar|a}} が法 {{Mvar|m}} に関する[[既約合同類群]] <math>(\mathbb{Z}/m\mathbb{Z})^{\times}</math> に入るための[[必要十分条件]]が {{Mvar|a}} が {{Mvar|m}} と互いに素であることから従う。従って、モジュラ逆数が直接的に
:<math>a^{\varphi(m)-1} \equiv a^{-1} \pmod{m}</math>
と求まる。これから、{{Mvar|m}} が素数である特別の場合には、{{Math|1=''φ''(''m'') = ''m'' &minus; 1}} ゆえ
: <math> a^{-1} \equiv a^{m-2} \pmod{m}</math>
となる。この方法は一般には拡張ユークリッド互除法よりも遅いが、冪剰余の実装が使える場合には利用されることがある。この方法が不利な点としては、
* {{Math|''φ''(''m'')}} を知るために {{Mvar|m}} の効率的な[[素因数分解]]ができなければならないが、一般には素因数分解は困難である（いくつかの自明な例を除く：例えば {{Mvar|m}} が素数あるいは素数冪の場合）
* 冪乗の計算コスト。[[冪剰余]]を用いてより効率的に実装できるが、{{Mvar|m}} の値が大きいときには[[モンゴメリ乗算|モンゴメリ法]]を用いるのが最も効率的である。モンゴメリ法自体が、そもそも目的であった法 {{Mvar|m}} でのモジュラ逆数を用いている。モンゴメリ法を用いない場合、冪乗の計算に標準的な[[バイナリ法]]を用いると、各ステップで法 {{Mvar|m}} での除法を行う必要があるため、{{Mvar|m}} が大きくなるほど遅くなる。

== 応用 ==
モジュラ逆数を見つけるという操作は、モジュラ計算を使ったアルゴリズムに多く応用されている。例えば、暗号技術ではモジュラ演算を用いることで、演算をより早く、より少ない記憶容量で行う部分と、演算がより困難な部分がある。<ref name=":0">{{harvnb|Trappe|Washington|2006|loc=p. 167}}</ref>これら二つの性質は共に利点として利用できる。特に[[RSA暗号]]では、暗号化・復号には適切に選ばれたモジュラ逆数となる2つの数が使われる。2つのうち1つは公開し、暗号化するために使用される。もう1つは安全に保管しておき、復号に使用する。ここまでの処理は高速だが、1つ目の[[公開鍵暗号|公開鍵]]から2つ目の秘密鍵を作るには非現実的な計算コストは避けられないと考えられており、このことがRSA暗号の仕組みを支えている。<ref name=":1">{{harvnb|Trappe|Washington|2006|loc=p. 165}}</ref>

ほかの変わった例を一つ挙げる。[[ワード]]のサイズの、kの倍数で奇数である整数を要素に持つ（長い）リストがあったとする。ここで、これらの数をすべてkで割りたい。実装の一つとして次のようなものがある。

# <math>k^{-1}\pmod{2^w}</math> を[[ユークリッドの互除法#%E6%8B%A1%E5%BC%B5%E3%81%95%E3%82%8C%E3%81%9F%E4%BA%92%E9%99%A4%E6%B3%95|拡張ユークリッド互除法]]を用いて計算する（''w''はワードのbit数、通常32）。<math>\gcd(2^w, k)=1</math>であるから、これは必ず存在する。
# リストの各要素に<math>k^{-1}</math>を掛け、下位 ''w'' bit に相当する部分を取り出す（つまり<math>2^w</math>で割った余りをとる）。

除算をハードウェアで実装していない処理系にとって、除算は掛け算に比べて遅く、この方法によって格段に処理速度を速めることができる。手順1.には時間はかかるが1回で済むため、扱うリストのサイズが大きければそれだけ効率的である。

このほかモジュラ逆数を用いて、[[中国の剰余定理]]によって存在が保証されている[[合同式|合同方程式]]の解を求めることができる。

例えば、合同方程式 

:<math>X\equiv 4 \pmod{5}</math>
:<math>X\equiv 4 \pmod{7}</math>
:<math>X\equiv 6 \pmod{11}</math>

は 5, 7, 11 が[[互いに素 (整数論)|互いに素]]であり解をもつ。解は

:<math>X=t_1(7\times 11)\times 4 + t_2(5\times 11)\times 4 + t_3(5\times 7)\times 6</math>

であり

:<math>t_1=(7\times 11)^{-1}\pmod{5} = 3</math>
:<math>t_2=(5\times 11)^{-1}\pmod{7} = 6</math>
:<math>t_3=(5\times 7)^{-1}\pmod{11} = 6</math>

である。上記の合同方程式を満たしていることは容易にわかる。よって

:<math>X\equiv 3504\equiv 39 \pmod{385}</math>

385 は 5, 7, 11 の最小公倍数である。

また、モジュラ逆数は{{仮リンク|Kloosterman和|en|Kloosterman sum}}の定義で重要な位置を占めている。

== 関連項目 ==
* [[逆数合同法]]
* [[合同算術]]
* [[剰余演算]]
* [[整数の合同]]
* [[初等数論]]
* [[公開鍵暗号]]
* [[ユークリッドの互除法]]

== 参考文献 ==
{{reflist}}

{{DEFAULTSORT:もしゆらきやくすう}}
[[Category:合同算術]]
[[Category:数学に関する記事]]