オイラーの定理の利用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/15 03:40 UTC 版)
「モジュラ逆数」の記事における「オイラーの定理の利用」の解説
拡張ユークリッド互除法の代わりにオイラーの定理をモジュラ逆数の計算に利用することもできる。 オイラーの定理によれば、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 が大きくなるほど遅くなる。
※この「オイラーの定理の利用」の解説は、「モジュラ逆数」の解説の一部です。
「オイラーの定理の利用」を含む「モジュラ逆数」の記事については、「モジュラ逆数」の概要を参照ください。
- オイラーの定理の利用のページへのリンク
