1. 序章


このチュートリアルでは、拡張ユークリッド互除法（EEA）について説明します。 これは暗号化で広く使用されているツールであり、数論の基本的なアルゴリズムの1つです。 再帰バージョンに加えて、反復バリアントを紹介します。


2. ベズーのアイデンティティ








ベズーのアイデンティティは、任意の2つの整数の最大公約数（GCD）が線形結合であると述べています。 したがって、がとのGCDである場合、整数などが存在します。


 (1)    


たとえば、ifと、thenと：


      


拡張ユークリッドアルゴリズム（EEA）は、とを検出します。これは、ベズーの係数とと呼ばれます。 後で説明するように、EEAは、2つの数値のGCDを見つけるためのユークリッドアルゴリズムの修正です。


2.1. 仮定


以下では、とが両方とも正であり、それであると仮定します。 これらの仮定の下では、次の理由で一般性が失われることはありません。


      


これは、ケースのみを検討できることを意味します。


    

  • とのいずれかがゼロの場合、もう一方の数値をGCDとして出力し、対応する係数をとに設定します。
    • 

  • （または）が負の場合、絶対値に置き換えます。
    • 

  • 最後に、とを切り替えることができます。
    • 



3. ユークリッドの互除法（EA）


ユークリッドの互除法（EA）は、次の事実を使用して、のGCDを検出します。


      


余りとしてゼロになるまで除法の原理を適用します。


      


最後のゼロ以外の剰余（）はとのGCDです。ご覧のとおり、再帰は次のとおりです。


 (2)    


どこ 。 剰余を被除数と除数で表すように、再帰ルールを再定式化すると便利です。


 (3)    


4. 拡張ユークリッドアルゴリズムの再帰バージョン


EAの再帰的拡張（REEA）は、入力番号のGCDとを計算するまで、通常のEAと同じように実行されます。 その時点で、それは最初に戻り始め、後方の分割ステップを再検討します。 除算ステップに戻った後、REEAはGCDをステップの除数と被除数の組み合わせとして表現します。


したがって、最後から2番目の部門から、次のようになります。


      


さて、に戻ると、に置き換えられるので、次のようになります。


      


一般に、分割ステップを再検討し、との線形結合として表現したとしましょう。


 (4)    


1ステップ戻ると、式（4）で次のように代入します。


 (5)    


したがって、次の後方再帰ルールを取得します。


 (6)    


最終的にGCDをとの線形結合として表すまで、除算ステップを逆方向に適用します。




4.1. 例


それを言ってみましょう。 アルゴリズムを適用して、5つの除法の原理を実行します。


      


または、繰り返しを使用する（3）：


      


GCDを識別した後、1つの除算ステップに戻ります。 そこから、私たちは一歩上に登って、何に置き換えるかを確認します。




いくつかの初等代数の後、それを取得します。 次に、もう一度ステップを上げて、何を置き換えるかを確認します。




と取得します。 最後に、最初の分割ステップに戻ります。




ベズーの係数を取得します。


 (7)    


5. 拡張ユークリッドアルゴリズムの反復バージョン


バックトラックなしで係数を計算できます。 アイデアは、各ステップの余りをとの線形結合として表現することです。 そのためには、次のことに注意することから始めます。


      


一般的に、次のようになります。


 (8)    


前のステップの係数を前提として、ステップの係数を計算するためのルールが必要です。 結局のところ、必要なのは前の2つのステップの係数だけです。それで、、、、を知っていると仮定しましょう。


      


式（3）を使用すると、次のようになります。


 (9)    


したがって、これらは係数の前方回帰です。


 (10)    


 GCDを計算するまで、除算のステップから始めて徐々に進めていきます。その時点で、求められているベズーの係数も取得します。




これは、ステップバイステップのように見える方法です。


この反復形式のEEAは、2つの数値のブランキンシップ法と同等です。これにより、EAが拡張され、2つだけでなくGCDとベズーの数値係数が検出されます。


5.1. 例


REEAの例を再利用してみましょう。 ここでは、除法の原理を実行しながら係数を計算します。 最初の剰余は、との直接線形結合です。




次に、で割ります。 次に、余りをとの線形結合として表現し、前の手順で取得した式に置き換えます。




このステップを繰り返す係数を取得します。 各除算ステップの後、現在の被除数と除数で剰余を表します。両方とも以前は剰余として表示されていたため、対応する線形結合に置き換えて式を簡略化します[X252X ]：




Wは、最終的にREEAの場合と同じ結果を取得しますが、再帰はありません。 一般に、反復バリアントは再帰呼び出しを回避し、同じフレームを維持するため、より高速である必要があります。


5.2. アルゴリズムの高速化


漸化式（10）からわかるように、-coefficientsと-coefficientsは互いに依存していません。 さらに、最終的な形から：


      


ファイナルがわかっていれば、ファイナルを計算できます。


      


とその逆。 したがって、除算ステップを実行するときに両方の係数を計算する必要はありません。 これにより、操作の数が3分の1に削減されます。


6. 係数はいくつありますか？


ベズーの係数は一意ではありません。実際、とのベズーの係数の1つのペアである場合、すべての係数は次の形式になります。


 (11)    


どこ 。


2つのペアのみが満たされます。


 (12)    


そしてEEAは常にそのようなペアを1つ見つけます。


7. 結論


この記事では、拡張ユークリッドアルゴリズムの再帰的および反復的な形式を紹介しました。 これは、2つの整数のベズーの係数を見つけるために使用され、暗号化に適用されます。