Thuật toán Euclide mở rộng

Bài toán tìm nghịch đảo modulo là một bước cực kỳ quan trọng trong mật mã học.

Định lý Bézout

Cho $a,b \in \mathbb N$và $\gcd(a,b)=1$, tồn tại $x,y \in \mathbb Z$ sao cho $ax+by=1$

Chứng minh

Xét tập hợp $S=\{ax+by \quad | x,y \in \mathbb Z, ax+by \gt 0\}$. Dễ dàng thấy rằng $S$ không rỗng.

Gọi $d$ là phần tử nhỏ nhất của $S$, vậy $d=ax_0 + by_0 \quad (x_0,y_0 \in \mathbb Z)$. Mục tiêu là ta sẽ chứng minh $d=1$.

Đầu tiên, ta chứng minh $d$ là ước số của $a$. thật vậy, ta có: $a=qd + r \quad (0 \le r \lt d)$, vậy $r=a-qd$, thay $d=ax_0 + by_0$ vào,
ta có:$r = a-q(ax_0 + by_0) = a(1-qx_0) + b(-qy_0)$

Như vậy, $r$ cũng có dạng $Aa+By$ do đó $r \in S$, mà $r<d$ vậy nhất định $r=0$, suy ra $d$ là ước số của $a$.

Tương tự, $d$ cũng là ước số của $b$. Mà ta có $\gcd(a,b)=1$ theo giả thuyết, vậy $d=1$, suy ra đpcm.

Nghịch đảo Modulo

Nghịch đảo modulo của $a$ theo modulo $m$ là số nguyên $x$sao cho $a.x \equiv 1 \mod m$.

Ta sẽ chuyển đổi để đưa từ bài toán kiếm nghịch đảo modulo của a về định lý Bézout: $ax \equiv 1\mod m \iff ax-1=my$ hay $ax - my=1$.

Điều kiện để tồn tại nghiệm là $\gcd(a,m)=1$

Thuật toán Euclide ngược

Ví dụ: Tìm nghịch đảo của $67$ trong modulo $12$. Ta đi tìm $x,y\in \mathbb Z: 67x + 12y = 1$.

Chiều xuôi, liên tục chia lấy dư số lớn cho số bé để tìm các số dư:

• 67 chia 12 dư 7

• 12 chia 7 dư 5

• 7 chia 5 dư 2

• 5 chia 2 dư 1 ngừng

Ta thu được các số dư là 2,5,7. Giờ ta đi tính ngược lên để tìm nhân tử Bezout.

Bắt đầu với 2, ta có 1 = 5-2.2, mà 2=7-5.1, thay vào ta có 1=5-2(7-5.1)=3.5-7.2
Tiếp tục với 5 = 12 - 1.7, thay vào: 1=3(12-1.7)-2.7 = 3.12-5.7
Tiếp tục với 7 = 67 - 5.12, thay vào 1=3.12 - 5(67-5.12)=28.12-5.67

Như vậy $x=-5, y=28$. Vì $x=-5 \lt 0$ ta cộng thêm $12$ để làm $x=12+(-5)$.
Vậy $7$ chính là nghịch đảo của $67$ trong modulo $12$.

Demo