擴充歐幾里著愛演算法

佇歐幾里著算法內底，阮干焦利用每一步紮餘除法所得的餘數。擴展歐幾里著算法猶利用紮餘除法所得的生理，佇咧軋轉相除的同時嘛會用得著貝祖等式的中的 x、y 兩个係數。以擴展歐幾里著算法求得的係數是滿足清氣等式的上簡單數。

另外咧，擴展歐幾里著算法是一種自驗證算法，上尾一步得著的 $ s _ { i + 一 } $ 和 $ t _ { i + 一 } $（$ s _ { i + 一 } $ 和 $ t _ { i + 一 } $ 的含義見下文）乘以 $ \ gcd ( a , b ) $ 後恰為 $ a $ 和 $ b $，會當提來驗證計算結果有正確無。

擴展歐幾里著算法會當用來計算模反元素 ( 嘛叫模逆元 )，求出模反元素是 RSA 加密算法中獲得所需公鎖、私鎖的著愛步驟。

算法佮舉例

佇標準的歐幾里著算法內底，阮記要求上大公因數的兩個數為 $ a , b $，第 $ i $ 用步輦除法得著的商為 $ q _ { i } $，餘數為 $ r _ { i + 一 } $，則歐幾里著算法會當寫做是落形式：

$ { \ begin { aligned } r _ { 零 } &=a \ \ r _ { 一 } &=b \ \ & \ , \ , \ , \ vdots \ \ r _ { i + 一 } &=r _ { i 影一 }-q _ { i } r _ { i } \ quad { \ text { 而且 } } \ quad 零 \ leq r _ { i + 一 } < | r _ { i } | \ \ & \ , \ , \ , \ vdots \ end { aligned } } $

某乜步得著的 $ r _ { i + 一 }=零 $ 時，計算結束。頂一步得著的 $ r _ { i } $ 即為 $ a , b $ 的上大公因數。

擴展歐幾里著算法佇咧 $ q _ { i } $，$ r _ { i } $ 的基礎上增加兩組序列，記作 $ s _ { i } $ 和 $ t _ { i } $，並令 $ s _ { 零 }=一 $，$ s _ { 一 }=零 $，$ t _ { 零 }=零 $，$ t _ { 一 }=一 $，佇歐幾里著算法每步計算 $ r _ { i + 一 }=r _ { i 影一 }-q _ { i } r _ { i } $ 以外額外計算 $ s _ { i + 一 }=s _ { i 影一 }-q _ { i } s _ { i } $ 和 $ t _ { i + 一 }=t _ { i 影一 }-q _ { i } t _ { i } $，亦即：

$ { \ begin { aligned } r _ { 零 } &=a & r _ { 一 } &=b \ \ s _ { 零 } &=一 & s _ { 一 } &=零 \ \ t _ { 零 } &=零 & t _ { 一 } &=一 \ \ & \ , \ , \ , \ vdots & & \ , \ , \ , \ vdots \ \ r _ { i + 一 } &=r _ { i 影一 }-q _ { i } r _ { i } & { \ text { 而且 } } 零 & \ leq r _ { i + 一 } < | r _ { i } | \ \ s _ { i + 一 } &=s _ { i 影一 }-q _ { i } s _ { i } \ \ t _ { i + 一 } &=t _ { i 影一 }-q _ { i } t _ { i } \ \ & \ , \ , \ , \ vdots \ end { aligned } } $

算法結束條件佮歐幾里著算法一致，嘛是啦 $ r _ { i + 一 }=零 $，現此時所得的 $ s _ { i } $ 和 $ t _ { i } $ 就滿足等式 $ \ gcd ( a , b )=r _ { i }=as _ { i } + bt _ { i } $。

落去共表現 $ a=兩百四十 $，$ b=四十六 $ 為例演示矣擴展歐幾里著算法。所得的上大公因數是 $ 二 $，所得貝祖的等式為 $ \ gcd ( 兩百四十 , 四十六 )=二=ma九 * 兩百四十 + 四十七 * 四十六 $。同時猶閣有自驗證等式 $ | 二十三 | * 二=四十六 $ 和 $ | 鋪百二 | * 二=兩百四十 $。

這个過程嘛會當用初等變換表示。

$ $ { \ begin { pmatrix } 兩百四十 & 四十六 \ \ 一 & 零 \ \ 零 & 一 \ end { pmatrix } } \ rightarrow { \ begin { pmatrix } 十 & 四十六 \ \ 一 & 零 \ \ 鋪五 & 一 \ end { pmatrix } } \ rightarrow { \ begin { pmatrix } 十 & 六 \ \ 一 & 扳四 \ \ 鋪五 & 二十一 \ end { pmatrix } } \ rightarrow { \ begin { pmatrix } 四 & 六 \ \ 五 & 扳四 \ \ 鋪二十六 & 二十一 \ end { pmatrix } } \ rightarrow { \ begin { pmatrix } 四 & 二 \ \ 五 & ma九 \ \ 鋪二十六 & 四十七 \ end { pmatrix } } $ $

得著 $ ma九 \ times 兩百四十 + 四十七 \ times 四十六=二 $

證明

因為 $ 零 \ leq r _ { i + 一 } < | r _ { i } | $，$ r _ { i } $ 序列是一个遞減序列，所以本算法會當佇有限步內底終止。閣因為 $ r _ { i + 一 }=r _ { i 影一 }-r _ { i } q _ { i } $，$ ( r _ { i 影一 } , r _ { i } ) $ 和 $ ( r _ { i } , r _ { i + 一 } ) $ 的上大公因數是仝款的，所以終其尾得著的 $ r _ { k } $ 是 $ a $，$ b $ 的上大公因數。

佇歐幾里著算法正確的基礎頂面，閣對著 $ a=r _ { 零 } $ 和 $ b=r _ { 一 } $ 有等式 $ as _ { i } + bt _ { i }=r _ { i } $ 成立（_ i _=零抑是）。這个關係由下列遞推式對所有 $ i > 一 $ 成立：

$ r _ { i + 一 }=r _ { i 影一 }-r _ { i } q _ { i }=( as _ { i 影一 } + bt _ { i 影一 } )-( as _ { i } + bt _ { i } ) q _ { i }=( as _ { i 影一 }-as _ { i } q _ { i } ) + ( bt _ { i 影一 }-bt _ { i } q _ { i } )=as _ { i + 一 } + bt _ { i + 一 } $

所以 $ s _ { i } $ 和 $ t _ { i } $ 滿足喘氣等式，這就證明矣擴展歐幾里著算法的正確性。

實現

以下是擴展歐幾里德算法的 Python 實現：

擴展歐幾里著算法 C + + 實現：

參考資料

參考文獻

Thomas H . Cormen , Charles E . Leiserson , Ronald L . Rivest , and Clifford Stein . _ 算法導論 _ , Second Edition . MIT Press and McGraw-Hill , 兩千空一 . ISBN 空九二百六十二鋪三千二百九十三鋪七 . Pages 八仔五十九–八百六十一 of section 三十一孵二 : Greatest common divisor .
Christof Paar , Jan Pelzl 對馬小婷譯 . _ 深入淺出密碼學 _ , 清華大學出版社，ISBN 九九四七千八百七十三鋪空二百二十九九九九十六 . Pages 一百五十一孵一百五十五六桱三 . 第二擴展的歐幾里著算法

外部連結

Source for the form of the algorithm used to determine the multiplicative inverse in GF ( 二 ^ 八 )