拡張ユークリッドアルゴリズム

算術とコンピュータプログラミングにおいて、拡張ユークリッドアルゴリズムはユークリッドアルゴリズムの拡張であり、整数aとbの最大公約数(gcd)に加えて、ベズーの恒等式の係数 (次の条件を満たす整数xとy)も計算します。 $ax+by=\gcd(a,b)$ 一般的には次のように表記されます。 $\operatorname {xgcd} (a,b)$ 。

これは認証アルゴリズムです。なぜなら、この方程式を同時に満たし、入力を割り切ることができる唯一の数は最大公約数だからです。^{[ 1 ]}また、ほとんど追加コストをかけずに、 aとbをそれらの最大公約数で割った商を計算することもできます。

拡張ユークリッドアルゴリズムは、2 つの単変数多項式の最大公約数とベズーの恒等式の係数を計算するための非常によく似たアルゴリズムも指します。

拡張ユークリッドアルゴリズムは、 aとbが互いに素である場合に特に有用です。この場合、xはaの法bにおけるモジュラー乗法逆元であり、yはbの法aにおけるモジュラー乗法逆元です。同様に、多項式拡張ユークリッドアルゴリズムは、代数体拡張、特に非素数位数の有限体における乗法逆元を計算することを可能にします。したがって、拡張ユークリッドアルゴリズムはどちらも暗号学で広く使用されています。特に、モジュラー乗法逆元の計算は、RSA公開鍵暗号方式における鍵ペアの導出において不可欠なステップです。

説明

標準ユークリッドアルゴリズムは、商を使用せずにユークリッド除算を連続して行うことで進行します。余りだけが保持されます。拡張アルゴリズムでは、連続する商が使用されます。より正確には、入力としてaとbを用いた標準ユークリッドアルゴリズムは、一連の計算から成ります。 $q_1, ..., q_k$ 商と数列 $r_{0},\ldots ,r_{k+1}$ 余りの

{\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(this defines }}q_{i})\\&\,\,\,\vdots \end{aligned}}

ユークリッド除法の主な性質は、右側の不等式が一意に定義することである。 $q_{i}$ そして $r_{i+1}$ から $r_{i-1}$ そして $r_{i}.$

計算は、余りが出た時点で停止します。 $r_{k+1}$ つまりゼロです。最大公約数は、最後に残ったゼロ以外の余りです。 $r_{k}.$

拡張ユークリッドアルゴリズムも同様の手順で進みますが、次の2つのシーケンスが追加されます。

{\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{and }}0&\leq r_{i+1}<|r_{i}|&{\text{(this defines }}q_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}

計算は、 $r_{k+1}=0$ そして与える

$r_{k}$ 入力の最大公約数 $a=r_{0}$ そして $b=r_{1}.$
ベズー係数は $s_{k}$ そして $t_{k},$ それは $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$
aとbをそれらの最大公約数で割った商は次のように表される。 $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ そして $t_{k+1}=\mp {\frac {a}{\gcd(a,b)}}$ （看板） $\mp$ 反対 $\pm$ )

さらに、aとbが両方とも正で、 $\gcd(a,b)\neq \min(a,b)$ 、それから

|s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor

のために $0\leq i\leq k,$ どこ $\lfloor x\rfloor$ $はx$ の整数部分、つまり $x$ を超えない最大の整数を表します。

これは、拡張ユークリッドアルゴリズムによって得られるベズー係数のペアが、上記の2つの不等式を満たす唯一のペアであるため、最小のベズー係数のペアであることを意味します。

これはまた、aとbが符号なし整数データ型に収まる場合、コンピュータプログラムは対応する符号付き整数型で整数オーバーフローなしにベズー係数を計算できることを意味します。

例

次の表は、入力240と46に対する拡張ユークリッドアルゴリズムの進行状況を示しています。最大公約数は、列「余り」の最後の非ゼロエントリである2です。行 6 の余りが0であるため、計算は行 6 で停止します。ベズー係数は、最後から 2 番目の行の最後の 2 つの列に現れます。実際、 −9 × 240 + 47 × 46 = 2であることは簡単に確認できます。最後に、最後の行の最後の 2 つのエントリ 23と−120は、符号を除いて、入力46と240を最大公約数2で割った商です。

次の例では、より簡潔な表記法を使用しています。 $a=68$ そして $b=30$ 次のように計算できます。

g=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;\;^{\uparrow }\!\!-\!-\!(-2)}{(68,30)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!(-3)\!-\!\!-\!^{\uparrow }\;\;}{(8,30)}}

=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;^{\uparrow }\!\!-\!\!-\!(-1)\!\!}{(8,\,6)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!\!(-3)\!-\!\!-\!^{\uparrow }\;}{(2,\,6)}}=\mathrm {gcd} (2,0)=2,

どこ $\color {Green}\scriptstyle \,^{\uparrow }\!\!-\!-\!(-2)$ 最初のステップでは、 $-2$ タイムズ $30$ 追加される $68$ （一方の数の倍数をもう一方の数に加えた場合、最大公約数は変化しません。）

緑色で示された倍数の加算を方程式に同様に適用し、 $a=1a+0b$ そして $b=0a+1b,$ につながる $g=4a-9b,$ 隣接する計算によると（対応する右端の表は行演算を使用しています）。

証拠

以来 $0\leq r_{i+1}<|r_{i}|$ シーケンス $r_{i}$ は、非負整数の厳密に減少する数列である。 $i\geq 2$ したがって、それは何らかの形で停止しなければならない $r_{k+1}=0$ これは、アルゴリズムが最終的に停止することを証明している。

方程式から $r_{i+1}=r_{i-1}-r_{i}q_{i}$ したがって、 $\gcd(r_{i-1},r_{i})=\gcd(r_{i},r_{i+1})$ その結果、 $\gcd(a,b)=\gcd(r_{0},r_{1})=\gcd(r_{k},r_{k+1})=\gcd(r_{k},0)=r_{k}$ ここまでは、証明は古典的なユークリッドの互除法と同じです。

漸化式は、 $i\geq 0$ 、

${\begin{cases}r_{i}&=as_{i}+bt_{i}\\(-1)^{i}&=s_{i}t_{i+1}-t_{i}s_{i+1}\end{cases}}$

帰納法によって証明できる。実際、 $i=0$ それらは

${\begin{cases}r_{0}&=a=as_{0}+bt_{0}\\1&=(-1)^{0}=1\cdot 1-0\cdot 0=s_{0}t_{1}-t_{0}s_{1}\end{cases}}$

彼らが満足していると仮定すると $i$ 、方程式 $i+1$ 計算結果から

${\begin{cases}r_{i+1}&=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}\\(-1)^{i+1}&=-(s_{i}t_{i+1}-t_{i}s_{i+1})=s_{i+1}(t_{i}-q_{i+1}t_{i+1})-t_{i+1}(s_{i}-q_{i+1}s_{i+1})=s_{i+1}t_{i+2}-t_{i+1}s_{i+2}\end{cases}}$

特に、方程式 $s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}$ 示しているのは $s_{k+1}$ そして $t_{k+1}$ 互いに素である。

乗算 $0=r_{k+1}=as_{k+1}+bt_{k+1}$ による $s_{k}$ それは、

$0=as_{k+1}s_{k}+bt_{k+1}s_{k}=as_{k+1}s_{k}+b((-1)^{k}+t_{k}s_{k+1})$

したがって、 $b=(-1)^{k+1}(t_{k}-as_{k})s_{k+1}$ そこから次のことが導かれる。 $s_{k+1}$ 分ける $b$ 結果として、整数が存在する $d$ そのため $b=ds_{k+1}$ で割る $s_{k+1}$ 関係 $as_{k+1}+bt_{k+1}=0$ 与える $a=-dt_{k+1}.$ したがって、 $s_{k+1}$ そして $-t_{k+1}$ は互いに素な整数であり、 $a$ そして $b$ 共通因数によって、つまりそれらの最大公約数またはその反対によって。

最後の主張を証明するために、 $a$ そして $b$ どちらも肯定的で $\gcd(a,b)\neq \min(a,b)$ 。それから、 $a\neq b$ 、そしてもし $a<b$ すると、 EEA の下での( a , b ) のsおよびtシーケンスは、最初の 0 および 1 を除いて、( b , a ) のtおよびsシーケンスであることがわかります。定義から、( a , b ) の場合が ( b , a ) の場合に帰着することがわかります。したがって、 $a>b$ 一般性を損なうことなく。

分かるように $s_{2}$ 1であり、 $s_{3}$ （ $\gcd(a,b)\neq \min(a,b)$ ) は負の整数です。その後、 $s_{i}$ 符号が交互に変化し、絶対値が厳密に増加する。これは定義と事実から帰納的に導かれる。 $q_{i}\geq 1$ のために $1\leq i\leq k$ ケース $i=1$ 保持する理由は $a>b$ 同じことが $t_{i}$ 最初の数項の後、同じ理由で。さらに、 $q_{k}\geq 2$ ( aとbが両方とも正で、 $\gcd(a,b)\neq \min(a,b)$ したがって、 $|s_{k+1}|=|s_{k-1}|+q_{k}|s_{k}|$ 我々は得る $|s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.$

これに加えて、 $s_{k},t_{k}$ 絶対値がこれまでのどの値よりも大きいか等しい $s_{i}$ または $t_{i}$ それぞれ証明を完了した。

多項式拡張ユークリッドアルゴリズム

体上の係数を持つ単変数多項式の場合、ユークリッド除法、ベズーの恒等式、拡張ユークリッド互除法など、すべて同様に機能します。最初の違いは、ユークリッド除法と互除法では不等式が $0\leq r_{i+1}<|r_{i}|$ 次数に関する不等式に置き換える必要がある $\deg r_{i+1}<\deg r_{i}.$ それ以外の点では、この記事のこれまでの内容はすべて同じで、単に整数を多項式に置き換えるだけです。

2つ目の違いは、拡張ユークリッドアルゴリズムによって提供されるベズー係数の大きさの上限にあり、これは多項式の場合にはより正確であり、次の定理につながります。

a と b が 2 つの非ゼロ多項式である場合、拡張ユークリッドアルゴリズムは、次の条件を満たす一意の多項式のペア( s , t )を生成します。

as+bt=\gcd(a,b)

そして

\deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).

3つ目の違いは、多項式の場合、最大公約数はゼロでない定数による乗算を除いてのみ定義されるという点です。最大公約数を明確に定義する方法はいくつかあります。

数学では、最大公約数が単項式であることを要求するのが一般的です。これを得るには、出力の各要素をの最高次係数で割れば十分です。 $r_{k}.$ これにより、aとbが互いに素であれば、ベズーの不等式の右辺は1になります。そうでなければ、任意の非ゼロ定数が得られます。数式処理では、多項式の係数は一般的に整数であり、この方法で最大公約数を正規化すると、分数が多すぎて便利ではありません。

整数係数を持つ多項式の場合の最大公約数を正規化する 2 番目の方法は、すべての出力を次の内容で割ることです。 $r_{k},$ 原始的な最大公約数を取得するため。入力多項式が互いに素である場合、この正規化によって最大公約数は 1 になります。この方法の欠点は、計算中に多くの分数を計算して簡略化する必要があることです。

3つ目のアプローチは、ユークリッドの互除法を拡張ユークリッドの互除法に拡張するのと同様の方法で、部分結果擬似剰余数列のアルゴリズムを拡張することです。これにより、整数係数の多項式から始めると、計算されるすべての多項式が整数係数になります。さらに、計算されたすべての剰余は、 $r_{i}$ は部分終結多項式です。特に、入力多項式が互いに素である場合、ベズーの恒等式は次のようになります。

as+bt=\operatorname {Res} (a,b),

どこ $\operatorname {Res} (a,b)$ はaとbの合成を表します。この形式のベズーの恒等式では、式に分母がありません。すべてを合成で割ると、古典的なベズーの恒等式が得られ、その中に現れる有理数に共通の分母が明示されます。

擬似コード

上記のアルゴリズムを実装するには、まず、各ステップでインデックス付き変数の最後の2つの値のみが必要であることに留意する必要があります。したがって、メモリを節約するために、各インデックス付き変数は2つの変数に置き換える必要があります。

簡略化のため、以下のアルゴリズム（およびこの記事の他のアルゴリズム）では並列代入を使用します。この機能を持たないプログラミング言語では、補助変数を使用して並列代入をシミュレートする必要があります。たとえば、最初のアルゴリズムでは、

(old_r, r) := (r, old_r - quotient × r)

と同等

prov := r; r := old_r - quotient × prov; old_r := prov;

他の並列代入についても同様です。これにより、以下のコードが得られます。

関数extended_gcd(a, b) (old_r, r) := (a, b) (old_s, s) := (1, 0) (old_t, t) := (0, 1) while r ≠ 0 do quotient := old_r div r (old_r, r) := (r, old_r − quotient × r) (old_s, s) := (s, old_s − quotient × s) (old_t, t) := (t, old_t − quotient × t) 出力"ベズー係数:", (old_s, old_t) 出力"最大公約数:", old_r 出力"最大公約数による商:", (t, s)

出力される、 aとbをそれらの最大公約数で割った商は、符号が間違っている場合があります。これは計算の最後に簡単に修正できますが、コードを簡略化するためにここでは修正していません。同様に、aまたはbのいずれかがゼロで、もう一方が負の場合、出力される最大公約数は負になるため、出力の符号をすべて変更する必要があります。

最後に、ベズーの恒等式において、 $ax+by=\gcd(a,b)$ 解くことができる $y$ 与えられた $a,b,x,\gcd(a,b)$ したがって、上記のアルゴリズムの最適化は、 $s_{k}$ シーケンス（ベズー係数が得られる） $x$ )、そして計算する $y$ 最後に：

関数extended_gcd(a, b) s := 0; old_s := 1 r := b; old_r := a while r ≠ 0 do quotient := old_r div r (old_r, r) := (r, old_r − quotient × r) (old_s, s) := (s, old_s − quotient × s) b ≠ 0 の場合、 bezout_t := (old_r − old_s × a) div b それ以外の場合 bezout_t := 0 出力「ベズー係数:」、(old_s、bezout_t) 出力「最大公約数:」、old_r

しかし、多くの場合、これは真の最適化とは言えません。前者のアルゴリズムは、機械整数（つまり、桁数の上限が固定された整数）で使用する場合、オーバーフローの影響を受けにくいのに対し、bezout_tの計算におけるold_s × aの乗算はオーバーフローする可能性があり、この最適化は最大サイズの半分未満で表現できる入力に限定されます。サイズに制限のない整数を使用する場合、乗算と除算に必要な時間は整数のサイズの2乗に比例して増加します。これは、「最適化」が小さな整数の乗算/除算のシーケンスを単一の乗算/除算に置き換えることを意味し、置き換えられる演算を合わせたよりも多くの計算時間を必要とします。

分数の簡略化

分数 $⁠ a / b ⁠$ $は、 a$ と $b$ が互いに素で、 $b$ が正である場合に、標準的な簡略化された形式になります。この標準的な簡略化された形式は、前の擬似コードの 3 つの出力行を置き換えることによって得られます。

 $s = 0$ の場合、 「ゼロ除算」と 出力します。 $s$  $< 0$ の場合、s  $:$  $= -$  $s$  ;  $t$  $:= -$  $t$  (負の分母を避けるため)  $s$  $= 1の$ 場合、  $-$  $t$  ( 1に等しい分母を避けるため) を出力します $。$  $-$  $t$  $/$  $s$ を出力します $。$

$このアルゴリズムの証明は、 s$ と $t$ が互いに素な整数であり、かつ $+$ $bt$ $= 0$ $で$ あるという事実に基づいている。したがって ${\frac {a}{b}}=-{\frac {t}{s}}$ 標準的な簡略化された形式を得るには、分母が正になるようにマイナス符号を移動するだけで十分です。

$bが$ $aを$ 割り切る場合、アルゴリズムは1回の反復のみを実行し、アルゴリズムの最後に $s = 1となります。出力が整数となるのはこの場合のみです。$

モジュラー構造における乗法逆数の計算

拡張ユークリッドアルゴリズムは、モジュラー構造、特にモジュラー整数や代数体拡大における乗法逆元を計算するための不可欠なツールである。後者の顕著な例としては、非素数位数の有限体が挙げられる。

モジュラー整数

$n$ が正の整数である場合、環 $Z / n Z は$ $、 n$ によるユークリッド除算の剰余、整数の加算および乗算の結果の $n$ $による剰余からなる集合{0, 1, ..., n -1}$ と同一視できます $。Z$ $/$ $n$ $Z$ の要素 $a は、$ $n$ と互いに素である場合に乗法逆元を持ちます (つまり、単元です) 。特に、 $n が$ 素数である場合、 $a は$ $n$ を法としてゼロでない限り乗法逆元を持ちます。したがって、 $Z$ $/$ $n$ $Z が体であるのは、$ $n が$ 素数である場合のみです。

ベズーの恒等式は、 $a$ と $nが$ 互いに素であるのは、ある整数 $s$ と $t$ が存在して、

ns+at=1

この恒等式を $n$ で割ると

at\equiv 1\mod n.

したがって、 $t 、より正確には$ $tを$ $n$ で割った余りは、 $aの$ $n$ を法とする乗法逆数である。

この問題に拡張ユークリッドアルゴリズムを適用するには、 $n$ のベズー係数は不要であり、したがって計算する必要がないことに注意する必要があります。また、nより小さい正の値を得るには、アルゴリズムによって提供される整数 $t が$ $| t | < n$ を満たすという事実を利用できます。つまり、 $t < 0$ の場合は、最後に $n を$ 加算する必要があります (例は「モジュラー乗法逆元」の記事にあります)。これにより、入力nが 1 より大きい整数である擬似コードが得られます。

関数inverse(a, n) t := 0; newt := 1 r := n; newr := a while newr ≠ 0 do 商 := r div newr (t, newt) := (newt, t − quotient × newt) (r, newr) := (newr, r − 商 × newr) r > 1の場合、 「a は可逆ではありません」 を返す。t < 0の場合 t := t + n tを返す

単純な代数体拡張

拡張ユークリッドアルゴリズムは、単純な代数体拡張における乗法逆元を計算するための主要なツールでもあります。暗号理論や符号理論で広く用いられている重要なケースの一つは、非素数位数の有限体です。実際、 $p$ が素数で $q$ $=$ $p$ $d$ $の場合、位数q$ の体は、次数 $d$ の既約多項式の根によって生成される $p$ 個の要素を持つ素体の単純な代数拡張となります。

体 $K$ の単純代数拡大 $L は、次数$ $d$ の既約多項式 $p$ の根によって生成され、商環と同一視することができる。 $K[X]/\langle p\rangle ,$ 、そしてその要素は次数が $d$ 未満の多項式と全単射で対応します。L における加算は多項式の加算です。L における乗算は、 $多項式$ $の$ 積を $p$ で除算したときの余りです。したがって、 $L$ における算術を完成させるには、乗法逆元を計算する方法を定義するだけで済みます。これは拡張ユークリッドアルゴリズムによって行われます。

このアルゴリズムは、モジュラー乗法逆元を計算するために上で示したアルゴリズムと非常によく似ています。主な違いは 2 つあります。まず、提供されるベズー係数の次数が常に $d$ より小さいため、最後から 1 行目は不要です。次に、入力多項式が互いに素である場合、提供される最大公約数は $Kの任意の非ゼロ要素である可能性があります。したがって、このベズー係数 (一般に正の次数を持つ多項式) は、この$ $K$ 要素の逆元で乗算する必要があります。以下の擬似コードでは、 $p$ は 1 より大きい次数の多項式であり、 $a$ は多項式です。

関数inverse(a, p) t := 0; newt := 1 r := p; newr := a while newr ≠ 0 do 商 := r div newr (r, newr) := (newr, r − 商 × newr) (t, newt) := (newt, t − quotient × newt) degree(r) > 0の場合、 「p は既約でないか、a は p の倍数である」と返します。（1/r）×tを返す

例

例えば、有限体 GF(2 ⁸ )を定義するために使用される多項式が $p = x 8 + x 4 + x 3 + x + 1$ であり、逆元を求める要素が $a = x 6 + x 4 + x + 1$ である場合、アルゴリズムを実行すると、次の表で説明する計算結果が得られます。 2 ⁿ位数の体では、体内のすべての要素zに対して− z = zおよびz + z = 0であることを思い出してください。 1 は GF(2 ) の唯一の非ゼロ要素であるため、擬似コードの最後の行の調整は必要ありません。

したがって、逆数は $x 7 + x 6 + x 3 + x$ であり、これは2 つの要素を掛け合わせて、その結果の余りを $p$ で割ることによって確認できます。

2つ以上の数字の場合

2 つ以上の数の場合を反復的に処理することができます。まず、以下を示します。 $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ これを証明するために $d=\gcd(a,b,c)$ 最大公約数の定義により $d$ はの約数です $a$ そして $b$ 。したがって $\gcd(a,b)=kd$ 一部の人にとって $k$ 同様に $d$ はの約数です $c$ それで $c=jd$ 一部の人にとって $j$ 。させて $u=\gcd(k,j)$ 我々の構築により $u$ 、 $ud|a,b,c$ しかし、 $d$ 最大の約数 $u$ は単位です。そして、 $ud=\gcd(\gcd(a,b),c)$ 結果は証明された。