拡張ユークリッド互除法

算術およびコンピュータプログラミングにおいて、拡張ユークリッドの互除法はユークリッドの互除法の拡張であり、整数aとbの最大公約数（gcd）に加えて、ベズーの恒等式の係数、つまり整数xとyを計算します。

${\displaystyle ax+by=\gcd(a,b).}$

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

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

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

標準ユークリッドアルゴリズムは、商が使用されないユークリッド除算の連続によって進行します。剰余のみが保持されます。拡張アルゴリズムでは、連続する商が使用されます。より正確には、 aとbを入力とする標準ユークリッドアルゴリズムは、商のシーケンスと剰余の シーケンスを計算し、${\displaystyle q_{1},\ldots ,q_{k}}$${\displaystyle r_{0},\ldots ,r_{k+1}}$

${\displaystyle {\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{(これは }}q_{i} を定義します)\\&\,\,\,\vdots \end{aligned}}}$

ユークリッドの除法の主な性質は、右側の不等式が一意に定義され、${\displaystyle q_{i}}$${\displaystyle r_{i+1}}$${\displaystyle r_{i-1}}$${\displaystyle r_{i}.}$

計算は余りがゼロになると停止します。最大公約数は最後のゼロでない余りになります。${\displaystyle r_{k+1}}$${\displaystyle r_{k}.}$

拡張ユークリッド互除法も同様に進行しますが、次の2つのシーケンスが追加されます。

${\displaystyle {\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}}|&{\text{(これは定義する}}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}}}$

計算は、次の場合にも停止し、 ${\displaystyle r_{k+1}=0}$

• ${\displaystyle r_{k}}$入力の最大公約数であり、${\displaystyle a=r_{0}}$${\displaystyle b=r_{1}.}$
• ベズー係数は、${\displaystyle s_{k}}$${\displaystyle t_{k},}$${\displaystyle \gcd(a,b)=r_{k}=as_{k}+bt_{k}}$
• aとbを最大公約数で割った商は次のように表される。${\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}}$${\displaystyle t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}}$

さらに、aとbがともに正で、 ${\displaystyle \gcd(a,b)\neq \min(a,b)}$

${\displaystyle |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 }$

ここではxの整数部、つまりx を超えない最大の整数を表します。 ${\displaystyle 0\leq i\leq k,}$${\displaystyle \lfloor x\rfloor }$

これは、拡張ユークリッドの互除法によって提供されるベズー係数のペアが、上記の不等式の両方を満たす唯一のペアであるため、ベズー係数の 最小ペアであることを意味します。

また、これは、 aとbよりも大きい固定サイズの整数を使用するコンピュータ プログラムによって、整数オーバーフローなしでアルゴリズムを実行できることも意味します。

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

のシーケンスは、非負の整数の減少シーケンスです ( i = 2 以降)。したがって、ある で停止する必要があります。これは、アルゴリズムが最終的に停止することを証明します。 ${\displaystyle 0\leq r_{i+1}$${\displaystyle r_{i}}$${\displaystyle r_{k+1}=0.}$

最大公約数はとに対して同じであるため 、これは、入力の最大公約数が の最大公約数と同じであることを示しています。これは、 がaとbの最大公約数であることを証明します。 (この時点までの証明は、古典的なユークリッドの互除法の証明と同じです。) ${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i},}$${\displaystyle (r_{i-1},r_{i})}$${\displaystyle (r_{i},r_{i+1}).}$${\displaystyle a=r_{0},b=r_{1}}$${\displaystyle r_{k},r_{k+1}=0.}$${\displaystyle r_{k}}$

およびのとき、 i = 0 および 1に対して成り立ちます。帰納法により、すべての に対して関係式が成り立ちます。 ${\displaystyle a=r_{0}}$${\displaystyle b=r_{1},}$${\displaystyle as_{i}+bt_{i}=r_{i}}$${\displaystyle i>1}$$${\displaystyle 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}.}$$

したがって、 および はベズー係数です。 ${\displaystyle s_{k}}$${\displaystyle t_{k}}$

マトリックスを考える $${\displaystyle A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.}$$

再帰関係は行列形式で書き直すことができる。 $${\displaystyle A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.}$$

行列 は単位行列で、その行列式は 1 です。前の式の右端の行列の行列式は -1 です。したがって、 の行列式は になります。特に、 の場合、これをベズーの恒等式として見ると、と は互いに素であることがわかります。上で証明した関係とユークリッドの補題は、がb を割り切ること、つまり、ある整数dに対して であることを示しています。関係で割ると になります。したがって、と は互いに素な整数であり、 aとb を共通因数で割った商であり、したがって、共通因数はそれらの最大公約数またはその逆です。 ${\displaystyle A_{1}}$${\displaystyle A_{i}}$${\displaystyle (-1)^{i-1}.}$${\displaystyle i=k+1,}$${\displaystyle s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.}$${\displaystyle s_{k+1}}$${\displaystyle t_{k+1}}$${\displaystyle as_{k+1}+bt_{k+1}=0}$${\displaystyle s_{k+1}}$${\displaystyle b=ds_{k+1}}$${\displaystyle s_{k+1}}$${\displaystyle as_{k+1}+bt_{k+1}=0}$${\displaystyle a=-dt_{k+1}.}$${\displaystyle s_{k+1}}$${\displaystyle -t_{k+1}}$

最後の主張を証明するには、aとb が両方とも正で であると仮定します。すると、となり、 であれば、EEA の下での( a , b ) のsシーケンスとtシーケンスは、最初の 0 と 1 を除けば、 ( b , a ) のtシーケンスとsシーケンスであることがわかります。定義により、 ( a , b ) の場合は ( b , a ) の場合に簡約されることがわかります。したがって、一般性を失うことなく と仮定します。 ${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle a\neq b}$${\displaystyle a<b}$${\displaystyle a>b}$

は 1 であり、（ によって存在する）は負の整数であることがわかります。その後、の符号が交互に変化し、 の大きさが厳密に増加します。これは、 の定義と の場合、 であるため が成立するという事実から帰納的にわかります。同じ理由で、最初の数項の後の についても同じことが言えます。さらに、 （aとbが両方とも正で の場合）であることは簡単にわかります。したがって、 であることに注目すると、 ${\displaystyle s_{2}}$${\displaystyle s_{3}}$${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle s_{i}}$${\displaystyle q_{i}\geq 1}$${\displaystyle 1\leq i\leq k}$${\displaystyle i=1}$${\displaystyle a>b}$${\displaystyle t_{i}}$${\displaystyle q_{k}\geq 2}$${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle |s_{k+1}|=|s_{k-1}|+q_{k}|s_{k}|}$$${\displaystyle |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}|.}$$

これには、絶対値が以前のものよりも大きいか等しいという事実が伴い、またはそれぞれ証明が完了しました。 ${\displaystyle s_{k},t_{k}}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$

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

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

aとbが2つの非ゼロ多項式である場合、拡張ユークリッドの互除法は、次の式で表される一意の多項式ペア（s、t）を生成する。

${\displaystyle as+bt=\gcd(a,b)}$

そして

${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}$

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

数学では、最大公約数が単項多項式であることが要求されるのが一般的です。これを得るには、出力のすべての要素を の主係数で割るだけで十分です。これにより、aとbが互いに素であれば、ベズーの不等式の右辺は 1 になります。そうでない場合は、ゼロ以外の任意の定数が得られます。コンピュータ代数では、多項式は一般に整数係数を持ち、最大公約数を正規化するこの方法では分数が多すぎて便利ではありません。 ${\displaystyle r_{k}.}$

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

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

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

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

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

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

(old_r, r) := (r, old_r - 商 * r)

は、

証明:= r;
r := old_r - 商 × prov;
古い_r := prov;

他の並列割り当てについても同様です。これにより、次のコードが生成されます。

関数extended_gcd(a, b)
    (古いr, r) := (a, b)
    (古いs, s) := (1, 0)
    (古いt, t) := (0, 1)
    
    r ≠ 0の場合、
        商 := old_r div rを実行します。
        (old_r, r) := (r, old_r − 商 × r)
        (old_s, s) := (s, old_s − 商 × s)
        (old_t, t) := (t, old_t − 商 × t)
    
    出力「ベズー係数:」、(old_s、old_t)
    出力「最大公約数:」、old_r
    出力「最大公約数による商:」、(t、s)

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

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

関数extended_gcd(a, b)
    s := 0; 古いs := 1
    r := b; 古いr := a
         
    r ≠ 0の場合、
        商 := old_r div rを実行します。
        (old_r, r) := (r, old_r − 商 × r)
        (old_s, s) := (s, old_s − 商 × s)
    
    b ≠ 0の場合bezout_t 
        := (old_r − old_s × a) div b
    それ以外の場合
        ベズアウト_t := 0
    
    出力「ベズー係数:」、(old_s、bezout_t)
    出力「最大公約数:」、old_r

しかし、多くの場合、これは実際には最適化ではありません。前のアルゴリズムは、マシン整数 (つまり、桁数の上限が固定された整数) で使用するとオーバーフローの影響を受けにくいのに対し、bezout_tの計算におけるold_s * aの乗算はオーバーフローする可能性があり、この最適化は最大サイズの半分未満で表現できる入力に制限されます。無制限のサイズの整数を使用する場合、乗算と除算に必要な時間は整数のサイズの 2 乗で増加します。これは、「最適化」によって、小さな整数の乗算/除算のシーケンスが 1 つの乗算/除算に置き換えられることを意味します。これにより、置き換えられる操作全体よりも多くの計算時間が必要になります。

分数⁠1つの/b⁠ は、 aとbが互いに素でbが正の場合には標準簡略形になります。この標準簡略形は、前述の擬似コードの出力行3つを次のように置き換えることで得られます。

 s = 0 の場合、 「ゼロ除算」
を出力します。s < 0の場合 、s  := − s ;   t  := − t    (負の分母を避けるため)
 s = 1の場合、 - tを出力します        (分母が1
にならないようにするため)出力⁠      - t/s⁠

このアルゴリズムの証明は、 sとt が互いに素な 2 つの整数であり、+ bt = 0であり、したがって であるという事実に依存しています。標準的な簡略化された形式を得るには、分母が正になるようにマイナス記号を移動するだけで十分です。 ${\displaystyle {\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を法として）、逆元を持つ。したがって、 nが素数の場合に限り、 Z / n Z は体である。

ベズーの恒等式は、aとnが互いに素であるのは、次の整数sとtが存在する場合のみであることを主張する。

${\displaystyle ns+at=1}$

この恒等式をnで割ると次のようになる 。

${\displaystyle at\equiv 1\mod n.}$

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

この問題に拡張ユークリッドの互除法を適用する場合、nのベズー係数は必要ないので、計算する必要がないことに注意する必要があります。また、正でnより小さい結果を得るには、アルゴリズムによって提供される整数tが| t | < nを満たすという事実を利用できます。つまり、t < 0の場合、最後にn を追加する必要があります。これにより、入力nが 1 より大きい整数である擬似コードが生成されます。

関数inverse(a, n)
    t := 0; ニュート := 1
    r := n; 新しいr := a

    while newr ≠ 0 do
        商 := r div newr
        (t, newt) := (newt, t − 商 × 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の根によって生成され、商環と同一視され、その要素は次数d未満の多項式と全単射に対応します。 Lの加算は、多項式の加算です。Lの乗算は、多項式の積のpによるユークリッド除算の剰余です。したがって、 Lの演算を完了するには、乗法逆数を計算する方法を定義するだけです。これは、拡張ユークリッドのアルゴリズムによって行われます。 ${\displaystyle K[X]/\langle p\rangle ,}$

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

関数inverse(a, p)
    t := 0; ニュート := 1
    r := p; 新しいr := a

    while newr ≠ 0 do
        商 := r div newr
        (r, newr) := (newr, r − 商 × newr)
        (t, newt) := (newt, t − 商 × newt)

    度数(r) > 0の場合、 
        「p は既約ではないか、a は p の倍数です」を返します。

    リターン（1/r）×t

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

したがって、逆数はx ⁷ + x ⁶ + x ³ + xであり、 2 つの要素を掛け合わせて、その結果の pによる剰余を取ることで確認できます。

2 つ以上の数のケースは反復的に処理できます。まず、 であることを示します。これを証明するには、 とします。 の定義により、gcd はおよびの約数です。したがって、ある に対して となります。同様に、はの約数であるため、ある に対してとなります。 とします。 の構築により、ですが、 であるため、最大の約数は1です。また、 であるため、結果は証明されています。 ${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c)}$${\displaystyle d=\gcd(a,b,c)}$${\displaystyle d}$${\displaystyle a}$${\displaystyle b}$${\displaystyle \gcd(a,b)=kd}$${\displaystyle k}$${\displaystyle d}$${\displaystyle c}$${\displaystyle c=jd}$${\displaystyle j}$${\displaystyle u=\gcd(k,j)}$${\displaystyle u}$${\displaystyle ud|a,b,c}$${\displaystyle d}$${\displaystyle u}$${\displaystyle ud=\gcd(\gcd(a,b),c)}$

すると、 そしてが存在するので、最終的な方程式は次 のようになります。${\displaystyle na+mb=\gcd(a,b)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}$

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,}$

そこでn個の数に適用するには帰納法を使う。

${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),}$

方程式はそのまま続きます。

• ユークリッド領域
• 線形合同定理
• クッタカ

• クヌース、ドナルド。『コンピュータプログラミングの芸術』。アディソン・ウェズリー。第2巻第4章。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Pressおよび McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 31.2: 最大公約数の 859 ～ 861 ページ。 

Wikibookアルゴリズム実装には、拡張ユークリッドアルゴリズムに関するページがあります。

• GF(2^8) の逆数を決定するために使用されるアルゴリズムの形式のソース