--- title: Extended GCD Algorithm tags: crypto lang: zh_tw --- * [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS) [TOC] # Extended GCD Algorithm 給此演算法 a, b 可以快速找到整數 x, y 符合下列式子 - $ax + by = gcd(a, b)$ 運用輾轉相除法 $\begin{split} &gcd(a,b) \\ &=gcd(b, r_1)\ \mathrm{// a = k_1b+r_1}\\ &=gcd(r_1, r_2)\ \mathrm{// b = k_2r_1+r_2}\\ &=gcd(r_2, r_3)\ \mathrm{// r_1 = k_3r_2+r_3}\\ &...\\ &=gcd(r_{n-3}, r_{n-2})\ \mathrm{// r_{n-4} = k_{n-2}r_{n-3}+r_{n-2}}\\ &=gcd(r_{n-2}, r_{n-1})\ \mathrm{// r_{n-3} = k_{n-1}r_{n-2}+r_{n-1}}\\ &=gcd(r_{n-1}, r_n)\ \mathrm{// r_{n-2} = k_{n}r_{n-1}+r_n}\\ &=gcd(r_n, 0)\ \mathrm{// r_{n-1} = k_{n+1}r_n + 0}\\ &= r_n \end{split}$ 反推 $\begin{split} gcd(a, b) = ax + by &= r_n\\ &= r_{n-2} - k_nr_{n-1}\\ &= (r_{n-4} - k_{n-2}r_{n-3}) - k_n(r_{n-3} - k_{n-1}r_{n-2})\\ \end{split}$ 如此一直往回追溯，就能變成跟 $x, y$ 有關的式子 ## 例子 $\begin{split} &gcd(a, b)\\ &=gcd(32,12) \\ &=gcd(12, 8)\ \mathrm{// a = 2b+8}\\ &=gcd(8, 4)\ \mathrm{// b = 1\times 8+4}\\ &=gcd(4, 0)\ \mathrm{// 8 = 2\times 4+0}\\ \end{split}$ 反推 $\begin{split} gcd(a, b) = gcd(32, 12) &= 4 \\ &= b - 8\\ &= b - (a - 2b)\\ &= -a + 3b\\ &= ax + by \end{split}$ 配出 $x=-1, y=3$