アルゴリズム論特論（塩田）2021年度

アルゴリズム論特論（塩田）第6回 (3)　逆数計算アルゴリズム

$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

$\newcommand{\binv}{\displaystyle{\frac{1}{b}}}$

逆数が存在するための条件

Th.6　法

$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$ で実行し、 $d=\gcd(b,n)$ と、 $d=bx+ny$ を満たす $x$ , $y$ を求める。
$d \neq 1$ ならば「逆数は存在しません」と表示し、終了。
$x$ を出力。

計算のテクニック　 Alg.7 では

$y$ は出力に関与しませんので、拡張ユークリッドを呼び出すよりも、拡張ユークリッドから

$y$ の計算式を除いた専用ルーティンを組んだ方が速くなります。