拡張ユークリッド互除法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/15 03:40 UTC 版)
「モジュラ逆数」の記事における「拡張ユークリッド互除法」の解説
法 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 − 1（m は 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) で、一般に冪乗の計算よりも効率的である。
※この「拡張ユークリッド互除法」の解説は、「モジュラ逆数」の解説の一部です。
「拡張ユークリッド互除法」を含む「モジュラ逆数」の記事については、「モジュラ逆数」の概要を参照ください。
- 拡張ユークリッド互除法のページへのリンク
