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

Bách khoa toàn thư mở Wikipedia

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

a*x+b*y=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:

Trong số học đã biết rằng nếu d=UCLN(a,b) thì tồn tại các số nguyên x, y sao cho

a*x+b*y = d

Mục lục 1 Cơ sở lý thuyết của giải thuật 1.1 Giải thuật 1.2 Ví dụ 2 Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành 2.1 Số nghịch đảo trong vành 2.2 Giải thuật 2.3 Ví dụ 2.4 Ứng dụng 3 Xem thêm 4 Liên kết ngoài

[sửa] Cơ sở lý thuyết của giải thuật

Giải thuật Eclid mở rộng kết hợp quá trình tìm ƯCLN(a,b) trong thuật toán Eclid 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₁ = b, chia r₀ cho r₁ được số dư r₂. Nếu r₂ = 0 thì dừng, nếu r₂ khác không, chia r₁ cho r₂ được số dư r₃, ...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 = 0.

r_o = q₁ * r₁ + r₂,0 < r₂ < r₁;

r₁ = q₂ * r₂ + r₃,0 < r₃ < r₂;

....;

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₁, nghĩa là

x_o = 1,x₁ = 0 và y_o = 0,y₁ = 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.

[sửa] Giải thuật

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ả mã:

Procedure Euclid_Extended (a,b)
Var Int x0:=1, x1:=0, y0=0,y1:=1;

While b>0 do {
     r:= a mod b 
     q:= a div b
     x:= x0-x1*q1
     y:= y0-y1*q1
     if r=0 then Break
     a:=b
     b:=r
     x0:=x1     
     x1:=x
     y0:=y1     
     y1:=y
}
   Return d:=b, x, y;

[sửa] Ví dụ

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

Bước i	ri	ri + 1	ri + 2	qi + 1	xi	xi + 1	xi + 2	yi	yi + 1	yi + 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

[sửa] Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành

[sửa] Số nghịch đảo trong vành

Trong lý thuyết số, vành được định nghĩa là vành thương của với quan hệ đồng dư theo môđun m (là quan hệ tương đương) mà các phần tử của nó là các lớp đồng dư theo mođun m (m là số nguyên dương lớn hơn 1). Ta cũng có thể xét chỉ với các đại diện của nó. Khi đó

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

Phần tử a của được gọi là khả nghịch trong hay khả nghịch theo mođun m nếu tồn tại phần tử a' trong sao cho a*a'=1 trong hay . 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 mođun 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 x là nghịch đảo của a theo mođun m. Do đó có thể tìm được phần tử nghịch đảo của a theo mođun m nhờ thuật toán Euclid mở rộng khi chia m cho a.

[sửa] Giải thuật

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*q1
     m:=a
     a:=r
     y0:=y1     
     y1:=y
  }
 If a>1 Then Return "A không khả nghịch theo mođun m" 
 else Return " Nghịch dảo mođun m của a là y"

[sửa] 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 .

[sửa] Ứ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ã.

[sửa] Xem thêm

• Giải thuật Euclid

[sửa] 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.