Giải thuật Euclid mở rộng

Giải thuật Euclid mở rộng được sử dụng để giải một phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) có dạng

formula_1

Trong đó formula_2 là các hệ số nguyên, formula_3 là các ẩn nhận giá trị nguyên. Điều kiện cần và đủ để phương trình này có nghiệm (nguyên) là formula_4 là ước của formula_5. Khẳng định này dựa trên một mệnh đề sau:

"Nếu formula_6 thì tồn tại các số nguyên formula_3 sao cho formula_8

==Cơ sở lý thuyết của giải thuật==
Giải thuật Euclid mở rộng kết hợp quá trình tìm ƯCLN"(a, b)" trong thuật toán Euclid với việc tìm một cặp số x, y thoả mãn phương trình Đi-ô-phăng.
Giả sử cho hai số tự nhiên a, b, ngoài ra a>b>0.
Đặt formula_9, chia formula_10 cho formula_11 được số dư formula_12 và thương số nguyên formula_13. Nếu formula_14 thì dừng,
nếu formula_12 khác không, chia formula_11 cho formula_12 được số dư formula_18...Vì dãy các formula_19 là giảm thực sự nên sau hữu hạn bước ta được số dư formula_20.
trong đó số dư cuối cùng khác 0 là formula_25.
Bài toán đặt ra là tìm x, y sao cho 
Để làm điều này, ta tìm x, y theo công thức truy hồi, nghĩa là sẽ tìm
Ta có 
Tổng quát, giả sử có 
Khi đó từ
suy ra
từ đó, có thể chọn 
Khi formula_45 ta có được formula_46 và formula_47.
Các công thức (1), (2), (3) là công thức truy hồi để tính x, y.

===Giải thuật===
function gcd(a, b);
begin
end;
function Extended_gcd(a, b); 
begin
end;

Giải thuật sau chỉ thực hiện với các số nguyên a>b>0, biểu diễn bằng giải mã:

code
===Ví dụ===
Với a=29, b=8, giải thuật trải qua các bước như sau:

Kết quả thuật toán cho đồng thời formula_48 và formula_49, formula_50.
Dễ dàng kiểm tra hệ thức formula_51

==Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành formula_52==
===Số nghịch đảo trong vành formula_52===
Trong lý thuyết số, vành formula_52 được định nghĩa là vành thương của formula_55 với quan hệ đồng dư theo modulo m (là quan hệ tương đương) mà các phần tử của nó là các lớp đồng dư theo modulo m (m là số nguyên dương lớn hơn 1). Ta cũng có thể xét formula_52 chỉ với các đại diện của nó. Khi đó

formula_57

Phép cộng và nhân trong formula_58 là phép toán thông thường được rút gọn theo modulo m:

formula_59

formula_60

Phần tử a của formula_52 được gọi là khả nghịch trong formula_52 hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong formula_52 sao cho a*a'=1 trong formula_52 hay formula_65. Khi đó a' được gọi là nghịch đảo modulo m của a. Trong lý thuyết số đã chứng minh rằng, số a là khả nghịch theo modulo m khi và chỉ khi ƯCLN của a và m bằng 1.
Khi đó tồn tại các số nguyên x, y sao cho
Đẳng thức này lại chỉ ra y là nghịch đảo của a theo modulo m. Do đó có thể tìm được phần tử nghịch đảo của a theo modulo m nhờ thuật toán Euclid mở rộng khi chia m cho a.

===Giải thuật===
//a, m > 0. Trả về a^-1 mod m, gcd(a, m) phải bằng 1, chú ý là ta không cần quan tâm y khi giải pt diophante a * x + m * y = 1
function ModuloInverse(a, m);
begin
end;
Giải thuật sau chỉ thực hiện với các số nguyên m>a>0, biểu diễn bằng giã mã:

===Ví dụ===
Tìm số nghịch đảo (nếu có) của 30 theo môđun 101

Kết quả tính toán trong bảng cho ta formula_67. Lấy số đối của formula_68 theo mođun formula_69 được formula_70. Vậy formula_71.

===Ứng dụng===
Số nghịch đảo theo môđun được ứng dụng nhiều trong việc giải phương trình đồng dư, trong lý thuyết mật mã.

== Xem thêm ==
- Giải thuật Euclid

==Liên kết ngoài==
- A php implementation of the Extended Euclidean Algorithm showing line-by-line working and outputs
- A javascript implementation of the Extended Euclidean Algorithm shown above
- How to use the algorithm by hand
- Extended Euclidean Algorithm Applet
- Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)
- Source of a C++ program which calculates the multiplicative inverse.