アルゴリズム論特論（塩田）第6回 (3) 逆数計算アルゴリズム
逆数が存在するための条件
Th.6 法 $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}
\newcommand{\binv}{\displaystyle{\frac{1}{b}}}
n$ で $\binv$ が存在すること $\Leftrightarrow$ $\gcd(b,n)=1$
証明 $\Rightarrow$) $x=\binv$ とおくと定義より
$\exists\ y\ $ such that $\ b \times x = 1 + n \times y$
$\gcd(b,n)$ は $b$ と $n$ の公約数であるので
$1 = b \times x - n \times y$
の約数でもあり、$\gcd(b,n)=1$.
$\Leftarrow$) は次のアルゴリズムより。(証明終)
逆数計算アルゴリズム
Algorithm 7 (法 $n$ での逆数)
- 入力：$b$, $n$
- 出力：法 $n$ での $b$ の逆数 $\binv$
- 拡張ユークリッドアルゴリズムを引数 $b$, $n$ で実行し、$d=\gcd(b,n)$ と、$d=bx+ny$ を満たす $x$, $y$ を求める。
- $d \neq 1$ ならば「逆数は存在しません」と表示し、終了。
- $x$ を出力。
計算のテクニック
Alg.7 では $y$ は出力に関与しませんので、
拡張ユークリッドを呼び出すよりも、
拡張ユークリッドから $y$ の計算式を除いた専用ルーティンを組んだ方が速くなります。