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

${\displaystyle ax+by=c}$

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

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

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

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

....;

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

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

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

${\displaystyle 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

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

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

Ta có

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

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

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

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

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

Khi đó từ

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

suy ra

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

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

${\displaystyle 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

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

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

Khi ${\displaystyle i=m-1}$ ta có được ${\displaystyle x_{m+1}}$ và ${\displaystyle 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 ${\displaystyle i}$	${\displaystyle r_{i}}$	${\displaystyle r_{i+1}}$	${\displaystyle r_{i+2}}$	${\displaystyle q_{i+1}}$	${\displaystyle x_{i}}$	${\displaystyle x_{i+1}}$	${\displaystyle x_{i+2}}$	${\displaystyle y_{i}}$	${\displaystyle y_{i+1}}$	${\displaystyle 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 ${\displaystyle d=UCLN(29,8)=1}$ và ${\displaystyle x=-3}$, ${\displaystyle y=11}$.
Dễ dàng kiểm tra hệ thức ${\displaystyle 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 ${\displaystyle \mathbb {Z} _{m}}$

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

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

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

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

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

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

${\displaystyle 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 ${\displaystyle -37}$. Lấy số đối của ${\displaystyle 37}$ theo mođun ${\displaystyle 101}$ được ${\displaystyle 64}$. Vậy ${\displaystyle 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

Tham khảo

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