✨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<r2; ::....; ::$r${m-1}=q_mrm+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+by = 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+by_i = r_i với $i\; =0,1,...$. Ta có ::$a$1+b0= a = r_o và $a$0+b1 =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+by_i = ri với $i\; =0,1,...$. ::$a*x${i+1}+by{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+byi) -q{i+1}(ax_{i+1}+by{i+1})=r{i+2} ::$a$(xi-q{i+1}x_{i+1})+b(yi-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}=yi-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-x1q y= y0-y1q 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:

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 $\backslash mathbb\{Z\}\_m$

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

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

$\backslash mathbb\{Z\}\_m\; =\; \backslash left\; \backslash \{\; 0,1,...,m-1\; \backslash right\; \backslash \}$ Phép cộng và nhân trong $\backslash mathbb\{Z\}m$ là phép toán thông thường được rút gọn theo modulo m: $a+b=(a+b)\; \backslash quad\; mod\; \backslash quad\; m$
$a*b=(a*b)\; \backslash quad\; mod\; \backslash quad\; m$ Phần tử a của $\backslash mathbb\{Z\}\_m$ được gọi là khả nghịch trong $\backslash mathbb\{Z\}\_m$ hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong $\backslash mathbb\{Z\}\_m$ sao cho a*a'=1 trong $\backslash mathbb\{Z\}\_m$ hay $a*a\text{'}\; \backslash equiv\; 1\backslash 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

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\}\backslash ,mod\backslash ,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ã.