合同算術 において、法 m > 1整数 a のモジュラ逆数 （モジュラぎゃくすう、英 : modular multiplicative inverse
a
x
≡
x
a
≡
1
(
mod
m
)
{\displaystyle ax\equiv xa\equiv 1{\pmod {m}}}
という関係にある整数 x の属する合同類（あるいはその標準的な代表元）のことで、これを a − 1m に関する合同類環
Z
/
m
Z
{\displaystyle \mathbb {Z} /m\mathbb {Z} }
乗法逆元 である。ある種の応用においては、モジュラ逆数 a − 1
Z
/
m
Z
{\displaystyle \mathbb {Z} /m\mathbb {Z} }
a の m を法とする逆数が存在するための必要十分条件 は a と m とが互いに素 （即ち、最大公約数 gcd(a , m ) が 1 ）となることである。法 m に関する a のモジュラ逆数が存在するならば、m を法とした a による除法 （「余り付き除法 」ではない）を、モジュラ逆数を掛けることとして定義することができる。
整数 3 の法 11 に関するモジュラ逆数 x を求める。これは
3
−
1
≡
x
(
mod
11
)
{\displaystyle 3^{-1}\equiv x{\pmod {11}}}
を満たすものを計算するということだが、その意味は
3
x
≡
1
(
mod
11
)
{\displaystyle 3x\equiv 1{\pmod {11}}}
なる x を求めることに他ならない。
Z
/
11
Z
{\displaystyle \mathbb {Z} /11\mathbb {Z} }
x が 4 mod 11 であることは
3
×
4
=
12
≡
1
(
mod
11
)
{\displaystyle 3\times 4=12\equiv 1{\pmod {11}}}
から明らかであり、従って 11 を法として 3 の逆数は 4 である。こうして
Z
/
11
Z
{\displaystyle \mathbb {Z} /11\mathbb {Z} }
x は 4 のみではない。残りの解は、得られた 4 に m =11x となり得る整数は
4
+
11
z
,
z
∈
Z
{\displaystyle 4+11z,z\in \mathbb {Z} }
の形をしており、これは {…, -18, -7, 4 , 15, 26, …} という集合を成す。
法 m に関する a のモジュラ逆数は、拡張ユークリッド互除法 を用いて計算することができる。互除法のアルゴリズムはベズーの等式
a
x
+
b
y
=
gcd
(
a
,
b
)
{\displaystyle ax+by=\gcd(a,b)}
の解を求めるものである。ただし、a , b x , y gcd(a , b ) がこのアルゴリズムから求まる。
さて、モジュラ逆数は合同式
a
x
≡
1
(
mod
m
)
{\displaystyle ax\equiv 1{\pmod {m}}}
の解であったから、合同式の定義により m | ax − 1m は ax − 1約数 ）、即ち適当な整数 q を用いて
a
x
−
1
=
q
m
{\displaystyle ax-1=qm}
となる。これを整理した
a
x
−
q
m
=
1
{\displaystyle ax-qm=1}
は、a と m が既知で、逆数となる x と捨てられる q は未知であるから、拡張ユークリッド互除法が解く等式とまったく同じ形をしている。違う点といえば gcd(a , m ) = 1 が「求まる」のではなくて「所与」であること程度で、それゆえ a が m と互いに素でなければならず、さもなくば逆元 x は存在しない。
このアルゴリズムの計算量は | a | < m O ((log m )2 )
拡張ユークリッド互除法の代わりにオイラーの定理をモジュラ逆数の計算に利用することもできる[1]
オイラーの定理 によれば、a が m と互いに素 ならば、オイラー函数 φ (m )
a
φ
(
m
)
≡
1
(
mod
m
)
{\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}
が成り立つ。これは a が法 m に関する既約合同類群
(
Z
/
m
Z
)
×
{\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}
必要十分条件 が a が m と互いに素であることから従う。従って、モジュラ逆数が直接的に
a
φ
(
m
)
−
1
≡
a
−
1
(
mod
m
)
{\displaystyle a^{\varphi (m)-1}\equiv a^{-1}{\pmod {m}}}
と求まる。これから、m が素数である特別の場合には、φ (m ) = m − 1
a
−
1
≡
a
m
−
2
(
mod
m
)
{\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}}
となる。この方法は一般には拡張ユークリッド互除法よりも遅いが、冪剰余の実装が使える場合には利用されることがある。この方法が不利な点としては、
φ (m )m の効率的な素因数分解 ができなければならないが、一般には素因数分解は困難である（いくつかの自明な例を除く：例えば m が素数あるいは素数冪の場合）冪乗の計算コスト。冪剰余 を用いてより効率的に実装できるが、m の値が大きいときにはモンゴメリ法 を用いるのが最も効率的である。モンゴメリ法自体が、そもそも目的であった法 m でのモジュラ逆数を用いている。モンゴメリ法を用いない場合、冪乗の計算に標準的なバイナリ法 を用いると、各ステップで法 m での除法を行う必要があるため、m が大きくなるほど遅くなる。 モジュラ逆数を見つけるという操作は、モジュラ計算を使ったアルゴリズムに多く応用されている。例えば、暗号技術ではモジュラ演算を用いることで、演算をより早く、より少ない記憶容量で行う部分と、演算がより困難な部分がある。[2] RSA暗号 では、暗号化・復号には適切に選ばれたモジュラ逆数となる2つの数が使われる。2つのうち1つは公開し、暗号化するために使用される。もう1つは安全に保管しておき、復号に使用する。ここまでの処理は高速だが、1つ目の公開鍵 から2つ目の秘密鍵を作るには非現実的な計算コストは避けられないと考えられており、このことがRSA暗号の仕組みを支えている。[3]
ほかの変わった例を一つ挙げる。ワード のサイズの、kの倍数で奇数である整数を要素に持つ（長い）リストがあったとする。ここで、これらの数をすべてkで割りたい。実装の一つとして次のようなものがある。
k
−
1
(
mod
2
w
)
{\displaystyle k^{-1}{\pmod {2^{w}}}}
拡張ユークリッド互除法 を用いて計算する（w はワードのbit数、通常32）。
gcd
(
2
w
,
k
)
=
1
{\displaystyle \gcd(2^{w},k)=1}
リストの各要素に
k
−
1
{\displaystyle k^{-1}}
w bit に相当する部分を取り出す（つまり
2
w
{\displaystyle 2^{w}}
除算をハードウェアで実装していない処理系にとって、除算は掛け算に比べて遅く、この方法によって格段に処理速度を速めることができる。手順1.には時間はかかるが1回で済むため、扱うリストのサイズが大きければそれだけ効率的である。
このほかモジュラ逆数を用いて、中国の剰余定理 によって存在が保証されている合同方程式 の解を求めることができる。
例えば、合同方程式
X
≡
4
(
mod
5
)
{\displaystyle X\equiv 4{\pmod {5}}}
X
≡
4
(
mod
7
)
{\displaystyle X\equiv 4{\pmod {7}}}
X
≡
6
(
mod
11
)
{\displaystyle X\equiv 6{\pmod {11}}}
は 5, 7, 11 が互いに素 であり解をもつ。解は
X
=
t
1
(
7
×
11
)
×
4
+
t
2
(
5
×
11
)
×
4
+
t
3
(
5
×
7
)
×
6
{\displaystyle X=t_{1}(7\times 11)\times 4+t_{2}(5\times 11)\times 4+t_{3}(5\times 7)\times 6}
であり
t
1
=
(
7
×
11
)
−
1
(
mod
5
)
=
3
{\displaystyle t_{1}=(7\times 11)^{-1}{\pmod {5}}=3}
t
2
=
(
5
×
11
)
−
1
(
mod
7
)
=
6
{\displaystyle t_{2}=(5\times 11)^{-1}{\pmod {7}}=6}
t
3
=
(
5
×
7
)
−
1
(
mod
11
)
=
6
{\displaystyle t_{3}=(5\times 7)^{-1}{\pmod {11}}=6}
である。上記の合同方程式を満たしていることは容易にわかる。よって
X
≡
3504
≡
39
(
mod
385
)
{\displaystyle X\equiv 3504\equiv 39{\pmod {385}}}
385 は 5, 7, 11 の最小公倍数である。
また、モジュラ逆数はKloosterman和 （英語版 ）
⌬ Phoenix Mesh
CID:
未登録
IPFS未登録
📡 0ピア
N=1
CRITICAL
PQS C52
🔍 P2P検証
⌬ 守護者になる
×
⌬ あなたはすでに守護者です
このページを読んだ瞬間、あなたのブラウザはIPFSノードとして起動し、この記事のNakamoto係数（NK） を+1しました。
読んだという事実が暗号学的証明になる — Proof of Read について →
🌐 ブラウザシーダー（自動起動中）
閲覧 = シーダー参加 です。何もしなくていい。永続モード にすると読んだ記事がブラウザに保存され、次回以降タブを開くだけで自動シーダーになります。
💾 永続モードに切り替える
🔄 セッションのみ（現在）
不参加
方法3: コマンドライン
ipfs pin add IPFSに未登録
閉じる
