---
# System prepended metadata

title: Extended GCD Algorithm
tags: [crypto]

---

---
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$