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

$ax+by=c$

Trong đó $a,b,c$ là các hệ số nguyên, $x,y$ 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à $UCLN(a,b)$ là ước của $c$. Khẳng định này dựa trên một mệnh đề sau:

Nếu $d=UCLN(a,b)$ thì tồn tại các số nguyên $x,y$ sao cho $ax+by=d$

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 $r_{o}=a,r_{1}=b$, chia $r_{0}$ cho $r_{1}$ được số dư $r_{2}$ và thương số nguyên $q_{1}$. Nếu $r_{2}=0$ thì dừng, nếu $r_{2}$ khác không, chia $r_{1}$ cho $r_{2}$ được số dư $r_{3}$,...Vì dãy các $r_{i}$ là giảm thực sự nên sau hữu hạn bước ta được số dư $r_{m+2}=0$.

$r_{o}=q_{1}*r_{1}+r_{2},0<r_{2}<r_{1}$;

$r_{1}=q_{2}*r_{2}+r_{3},0<r_{3}<r_{2}$;

....;

$r_{m-1}=q_{m}*r_{m}+r_{m+1},0<r_{m+1}<r_{m}$

$r_{m}=q_{m+1}*r_{m+1}$

trong đó số dư cuối cùng khác 0 là $r_{m+1}=d$. Bài toán đặt ra là tìm x, y sao cho

$a*x+b*y=r_{m+1}(=d)$

Để 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

$x_{i}$ và $y_{i}$ sao cho:

$a*x_{i}+b*y_{i}=r_{i}$ với $i=0,1,...$.

Ta có

$a*1+b*0=a=r_{o}$ và $a*0+b*1=b=r_{1}$, nghĩa là

$x_{o}=1,x_{1}=0$ và $y_{o}=0,y_{1}=1$. (1)

Tổng quát, giả sử có

$a*x_{i}+b*y_{i}=r_{i}$ với $i=0,1,...$.

$a*x_{i+1}+b*y_{i+1}=r_{i+1}$ với $i=0,1,...$.

Khi đó từ

$r_{i}=q_{i+1}*r_{i+1}+r_{i+2}$

suy ra

$r_{i}-q_{i+1}*r_{i+1}=r_{i+2}$

$(a*x_{i}+b*y_{i})-q_{i+1}*(a*x_{i+1}+b*y_{i+1})=r_{i+2}$

$a*(x_{i}-q_{i+1}*x_{i+1})+b*(y_{i}-q_{i+1}*y_{i+1})=r_{i+2}$

từ đó, có thể chọn

$x_{i+2}=x_{i}-q_{i+1}*x_{i+1}$ (2)

$y_{i+2}=y_{i}-q_{i+1}*y_{i+1}$ (3)

Khi $i=m-1$ ta có được $x_{m+1}$ và $y_{m+1}$. 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

{Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)}
function gcd(a, b);
begin
  while b ≠ 0 do
    begin
      r:= a mod b; a:= b; b:= r;
    end;
  Result:= a;
end;
{Thuật toán Euclide mở rộng: a, b không đồng thời bằng 0, trả về cặp (x, y) sao cho a * x + b * y = gcd(a, b)
Về tư tưởng là ghép quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclide.}
function Extended_gcd(a, b); 
begin
  (xa, ya):= (1, 0);
  (xb, yb):= (0, 1);
  while b ≠ 0 do
    begin
      q:= a div b;
      r:= a mod b; a:= b; b:= r; //Đoạn này giống thuật toán Euclide.
      (xr, yr):= (xa, ya) - q * (xb, yb); //Hiểu là: (xr, yr):= (xa, ya) "mod" (xb, yb);
      (xa, ya):= (xb, yb);
      (xb, yb):= (xr, yr);
    end;
  Result:= (xa, ya);
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ã:

 Sub Euclid_Extended(a,b)
 Dim x0, x, y,y1 As Single
    x0=1: x1=0: y0=0: y1=1
 
 While b>0
      r= a mod b 
      if r=0 then Exit While
      q= a / b
      x= x0-x1*q
      y= y0-y1*q
      a=b
      b=r
      x0=x1     
      x1=x
      y0=y1     
      y1=y
 Wend
    Me.Print d:=b, x, y
code
 End Sub

Ví dụ

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

Bước $i$	$r_{i}$	$r_{i+1}$	$r_{i+2}$	$q_{i+1}$	$x_{i}$	$x_{i+1}$	$x_{i+2}$	$y_{i}$	$y_{i+1}$	$y_{i+2}$
0	29	8	5	3	1	0	1	0	1	-3
1	8	5	3	1	0	1	-1	1	-3	4
2	5	3	2	1	1	-1	2	-3	4	-7
3	3	2	1	1	-1	2	-3	4	-7	11
4	2	1	0	2

Kết quả thuật toán cho đồng thời $d=UCLN(29,8)=1$ và $x=-3$, $y=11$.
Dễ dàng kiểm tra hệ thức $29*(-3)+8*11=1$

Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành $\mathbb {Z} _{m}$

Số nghịch đảo trong vành $\mathbb {Z} _{m}$

Trong lý thuyết số, vành $\mathbb {Z} _{m}$ được định nghĩa là vành thương của $\mathbb {Z}$ 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 $\mathbb {Z} _{m}$ chỉ với các đại diện của nó. Khi đó

$\mathbb {Z} _{m}=\left\{0,1,...,m-1\right\}$

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

$a+b=(a+b)\quad mod\quad m$
$a*b=(a*b)\quad mod\quad m$

Phần tử a của $\mathbb {Z} _{m}$ được gọi là khả nghịch trong $\mathbb {Z} _{m}$ hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong $\mathbb {Z} _{m}$ sao cho a*a'=1 trong $\mathbb {Z} _{m}$ hay $a*a'\equiv 1{\pmod {m}}$. 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

$m*x+a*y=1$

Đẳ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
  xa:= 1; xm:= 0;
  while m ≠ 0 do
    begin
      q:= a div m;
      xr:= xa - q * xm;
      xa:= xm;
      xm:= xr;
      r:= a mod m;
      a:= m;
      m:= r;
    end;
  Result:= xa;
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ã:

 Procedure Euclid_Extended (a,m)
int,  y0:=0,y1:=1;

While a>0 do {
     r:= m mod a 
     if r=0 then Break      
     q:= m div a
     y:= y0-y1*q
     y0:=y1     
     y1:=y
     m:=a
     a:=r
     
  }
 If a>1 Then Return "A không khả nghịch theo mođun m" 
 else Return " Nghịch đảo modulo m của a là y"

Ví dụ

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

Bước i	m	a	r	q	y0	y1	y
0	101	30	11	3	0	1	-3
1	30	11	8	2	1	-3	7
2	11	8	3	1	-3	7	-10
3	8	3	2	2	7	-10	27
4	3	2	1	1	-10	27	-37
5	2	1	0	.	.	.	.

Kết quả tính toán trong bảng cho ta $-37$. Lấy số đối của $37$ theo mođun $101$ được $64$. Vậy $30^{-1}\,mod\,101=64$.

Ứ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 Lưu trữ 2006-09-04 tại Wayback Machine
• A javascript implementation of the Extended Euclidean Algorithm shown above Lưu trữ 2006-09-04 tại Wayback Machine
• How to use the algorithm by hand Lưu trữ 2006-09-07 tại Wayback Machine
• Extended Euclidean Algorithm Applet Lưu trữ 2006-09-12 tại Wayback Machine
• 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. Lưu trữ 2007-03-11 tại Wayback Machine