アルゴリズム論特論(塩田)第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$
  1. 拡張ユークリッドアルゴリズムを引数 $b$, $n$ で実行し、$d=\gcd(b,n)$ と、$d=bx+ny$ を満たす $x$, $y$ を求める。
  2. $d \neq 1$ ならば「逆数は存在しません」と表示し、終了。
  3. $x$ を出力。
計算のテクニック  Alg.7 では $y$ は出力に関与しませんので、 拡張ユークリッドを呼び出すよりも、 拡張ユークリッドから $y$ の計算式を除いた専用ルーティンを組んだ方が速くなります。