拡張ユークリッド互除法

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

ax+by=\gcd(a,b).

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

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

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

説明

標準ユークリッドアルゴリズムは、商を用いないユークリッド除算を連続して行う。剰余のみが保存される。拡張アルゴリズムでは、連続する商が用いられる。より正確には、aとbを入力とする標準ユークリッドアルゴリズムは、商の列と剰余の列を計算する。 $q_{1},\ldots ,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}=\pm {\frac {a}{\gcd(a,b)}}$

さらに、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

ここで、は $x$ の整数部、つまり $x$ 以下の最大の整数を表します。 $0\leq i\leq k,$ $\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	商q _{i −1}	剰余r _i	s _i	t _i
0		240	1	0
1		46	0	1
2	240 ÷ 46＝5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10＝4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
4	10 ÷ 6＝1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4＝1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2＝2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

証拠

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

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

およびのとき、i = 0 および 1に対して関係が成り立ちます。のすべての場合において、関係は帰納的に導かれます。 $a=r_{0}$ $b=r_{1},$ $as_{i}+bt_{i}=r_{i}$ $i>1$ $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}.$

したがって、とはベズー係数です。 $s_{k}$ $t_{k}$

マトリックスを考えてみましょう $A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.$

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

行列は単位行列であり、その行列式は 1 です。前の式で右端の行列の行列式は -1 です。したがって、の行列式はとなります。特に、の場合、これをベズーの恒等式として見ると、とは互いに素であることがわかります。上で証明した関係とユークリッドの補題から、は $b$ を割り切ることがわかります。つまり、ある整数 $d$ に対してとなります。関係で割るととなります。したがって、とは互いに素な整数であり、 $a$ と $b を$ 共通因数で割った商です。つまり、共通因数はまたはその反意語です。 $A_{1}$ $A_{i}$ $(-1)^{i-1}.$ $i=k+1,$ $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ $s_{k+1}$ $t_{k+1}$ $as_{k+1}+bt_{k+1}=0$ $s_{k+1}$ $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 がともに正でであると仮定します。すると、となり、であれば、 EEA における( a , b ) のs列とt列は、最初の 0 と 1 を除けば、 ( b , a ) のt列とs列と同じであることがわかります。定義から、( a , b ) の場合が ( b , a ) の場合に帰着することが分かります。したがって、一般性を失うことなくであると仮定します。 $\gcd(a,b)\neq \min(a,b)$ $a\neq b$ $a<b$ $a>b$

は1であり、（によって存在する）は負の整数であることがわかる。その後、の符号が交互に変化し、の大きさが厳密に増加する。これは定義との場合、が成り立つという事実から帰納的に導かれる。なぜならであるからである。最初の数項以降についても、同じ理由で同じことが成り立つ。さらに、（ aとbがともに正での場合）であることは容易にわかる。したがって、であることに注目すると、 $s_{2}$ $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$ $\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つ目の違いは、多項式の場合、最大公約数は非ゼロの定数を乗じた部分までしか定義されないことです。最大公約数を明確に定義する方法はいくつかあります。

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

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

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

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

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

擬似コード

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

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

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

は以下と同等である

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

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

関数extended_gcd(a, b) (old_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のいずれかがゼロで、もう一方が負の場合、出力される最大公約数は負となり、出力の符号をすべて変更する必要があります。

最後に、ベズーの恒等式において、が与えられた場合、を解くことができることに注意してください。したがって、上記のアルゴリズムを最適化するには、ベズー係数を生成するシーケンスのみを計算し、最後にを計算します。 $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 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乗に比例して増加します。これは、「最適化」によって、小さな整数の乗算/除算のシーケンスが単一の乗算/除算に置き換えられることを意味します。これにより、置き換えられる演算全体よりも多くの計算時間が必要になります。

分数の簡略化

分数 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1つの/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$ で割った余りは、 $n$ を法とした $a$ の逆数です。

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

関数inverse(a, n) t := 0; newt := 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$ における演算を完了するには、乗法逆元を計算する方法を定義するだけでよい。これは拡張ユークリッド互除法によって行われる。 $K[X]/\langle p\rangle ,$

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

関数inverse(a, p) t := 0; newt := 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 8 + x 4 + x 3 + x + 1$ であり、 $a = x 6 + x 4 + x + 1$ がその逆元である場合、アルゴリズムを実行すると次の表に示す計算が行われます。 2 ⁿ位の体では、体内のすべての元zに対して− z = zおよびz + z = 0 が成り立つことを思い出してください。 1 は GF(2) の唯一の非ゼロ元であるため、擬似コードの最後の行の調整は必要ありません。

ステップ	商	r、新しい	s、ニュース	t、イモリ
		$p = x 8 + x 4 + x 3 + x + 1$	1	0
		$a = x 6 + x 4 + x + 1$	0	1
1	$\times 2 + 1$	$x 2 = p - a (x 2 + 1 )$	1	$x 2 + 1 = 0 - 1 \cdot (x 2 + 1 )$
2	$\times 4 + \times 2$	$x + 1 = a - x 2 (x 4 + x 2)$	$x 4 + x 2 = 0 - 1(x 4 + x 2)$	$x 6 + x 2 + 1 = 1 - (x 4 + x 2) (x 2 + 1)$
3	$x + 1$	$1 = x 2 - (x + 1) (x + 1)$	$x 5 + x 4 + x 3 + x 2 + 1 = 1 - (x + 1)(x 4 + x 2)$	$x 7 + x 6 + x 3 + x = (x 2 + 1) - (x + 1) (x 6 + x 2 + 1)$
4	$x + 1$	$0 = (x + 1) - 1 \times (x + 1)$	$x 6 + x 4 + x + 1 = (x 4 + x 2) - (x +1)(x 5 + x 4 + x 3 + x 2 +1)$

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

2つ以上の数字の場合

2つ以上の数の場合も反復的に処理できます。まず、であることを示します。これを証明するには、とします。gcd の定義により、はおよびの約数です。したがって、についてはとなります。同様に、はの約数であるため、についてはとなります。とします。の構築により、が最大約数であるため、は単位約数です。また、であるため、結果は証明されています。 $\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)$

となるので、最終的な方程式は $na+mb=\gcd(a,b)$ $x$ $y$ $x\gcd(a,b)+yc=\gcd(a,b,c)$

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

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

\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 ),

次の方程式が直接続きます。

参照

参考文献

^ McConnell, Ross; Mehlhorn, Kurt; Näher, Stefan; Schweitzer, Pascal. 「Certifying Algorithms」（PDF） . 2024年9月29日閲覧。

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

外部リンク

GF(2^8)の逆数を求めるアルゴリズムの形式の出典

[1] McConnell, Ross; Mehlhorn, Kurt; Näher, Stefan; Schweitzer, Pascal. 「Certifying Algorithms」（PDF） . 2024年9月29日閲覧。

v t e 数論的アルゴリズム
素数判定	AKS 4月ベイリー–PSW 楕円曲線ポックリントンフェルマールーカスルーカス・レーマールーカス・レーマー・リーゼルプロスの定理ペパンの二次フロベニウスソロヴァイ・シュトラッセンミラー・ラビン
素数生成	アトキンのふるいエラトステネスの篩プリチャードのふるいスンダラムのふるいホイール因数分解
整数因数分解	連分数法（CFRAC）ディクソンのレンストラ楕円曲線（ECM）オイラーのポラードのロー p − 1 p + 1 二次ふるい（QS）一般数体ふるい（GNFS）特殊番号フィールドふるい（SNFS）合理的なふるいフェルマーのシャンクスの正方形裁判部ショアズ
乗算	古代エジプト長さからつばトゥーム・クックシェーンハーゲ通りフューラーの
ユークリッド除算	バイナリチャンキングフーリエゴールドシュミットニュートン・ラプソン長さ短い SRT
離散対数	小さな一歩、大きな一歩ポラード・ローポラードカンガルーポリーグ・ヘルマン指数計算関数フィールドふるい
最大公約数	バイナリユークリッド拡張ユークリッドレーマーの
モジュラー平方根	チポラポックリントントネリ・シャンクスベルレカンプ
その他のアルゴリズム	チャクラヴァラコルナッキア 2乗による累乗整数平方根整数関係（LLL ; KZ）モジュラー指数モンゴメリ還元シューフトラクテンバーグシステム
イタリック体は、アルゴリズムが特殊形式数用であることを示す