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

Bản mẫu:Underlinked 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=\{0,1,...,m-1\}$

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)modm$
$a*b=(a*b)modm$

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^{\prime }\equiv 1(\mathrm{mod}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}mod101=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 Bản mẫu:Webarchive
• A javascript implementation of the Extended Euclidean Algorithm shown above Bản mẫu:Webarchive
• How to use the algorithm by hand Bản mẫu:Webarchive
• Extended Euclidean Algorithm Applet Bản mẫu:Webarchive
• 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. Bản mẫu:Webarchive