Thuật toán Euclide mở rộng

Nguồn:  http://nguyenduccuong.com/index.php/nckh/80-thut-toan-euclide-m-rng.html

Trong lý thuyết số, thuật toán Euclid là một thuật toán để xác định ước số chung lớn nhất (GCD – Greatest Common Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên). Điều quan trọng chủ yếu là nó không yêu cầu việc phân tích thành thừa số 2 số nguyên, và nó cũng mang ý nghĩa lớn vì nó là một trong những thuật toán cổ nhất được biết đến, từ thời Hy Lạp cổ đại.

Lịch sử của thuật toán Euclid

Thuật toán Euclid là một trong những thuật toán cổ nhất được biết đến, từ khi nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Tuy nhiên, thuật toán đã hầu như không được phát hiện ra bởi Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được biết đến bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).

Mô tả thuật toán

Cho 2 số tự nhiên a và b, không đồng thời bằng 0: kiểm tra nếu b bằng 0, thì a là ước chung lớn nhất (UCLN). Nếu không, lặp lại xử lý sử dụng b và phần còn lại sau khi lấy a chia cho b. Phần còn lại sau khi chia a cho b thường được viết là a mod b.

Các thuật toán này có thể sử dụng trong bất kì hoàn cảnh nào khi còn phần dư. Điều này bao gồm các nhóm đa thức như nhóm số nguyên Gauxơ. Thuật toán không chỉ áp dụng cho số tự nhiên mà còn áp dụng cho nhiều trường hợp tổng quát khác sẽ được mô tả chi tiết sau.

Sử dụng đệ quy

Sử dụng đệ quy, thuật toán có thể phát biểu như sau:

Sử dụng tính lặp lại

Thuật toán Euclid mở rộng

Bằng cách theo dõi thương tìm được trong suốt thuật toán, ta có thể xác định các số nguyên p và q với ap+bq=gcd(a,b). Điều này được biết đến như là thuật toán Euclid mở rộng.

Thuật toán nguyên bản

Thuật toán nguyên bản được mô tả bởi Euclid đã giải quyết vấn đề về phương diện hình học, sử dụng lặp phép trừ đúng hơn là phép mod

Chú ý rằng trong khi b có thể là 0 thì a không thể là 0, nếu không nó sẽ trở thành vòng lặp vô hạn. Thuật toán này không yêu cầu 1 biến phụ t.

Một ví dụ

Giả sử tính toán UCLN của 1071 và 1029 là 21. Nhắc lại “mod” nghĩa là phần dư sau phép chia.

Với thuật toán đệ quy sau:

Với thuật toán lặp:

Nhận xét rằng a  b trong mỗi lần gọi. Nếu ban đầu, b > a, không có vấn đề gì, trước hết ta chỉ cần hoán đổi 2 giá trị cho nhau, sau đó các bước hoàn toàn tương tự.

Chứng minh

Giả thiết a và b là các số tự nhiên mà UCLN phải xác định. Bây giờ, giả thiết b > 0, và phần dư của phép chia a cho b là r. Do đó a = qb + r với q là thương của phép chia.

Bất kì phép chia thông thường nào của a và b cũng cho một số dư r. Để thấy sự đúng đắn đó, ta coi r có thể được viết là r = a – qb. Bây giờ nếu có một ước chung d của a và b, như vậy a = sd và b = td, khi đó r = (s-qt)d, ta có thể thấy rằng r chia hết cho d.

Những phân tích trên là đúng cho bất kì số chia d nào, vì thế, UCLN của a và b cũng là UCLN của b và r. Do đó nếu ta tiếp tục tìm UCLN với các số b và r. Khi giá trị tuyệt đối của r nhỏ hơn b, ta sẽ tiến tới rn+1 = 0 sau nhiều bước.

Thời gian chạy

Khi phân tích thời gian chạy của thuật toán Euclid, ta bỏ qua các phép chia có đầu và là 2 số Fibonacci liên tiếp (vì tỉ số của chúng hội tụ rất chậm …), và trường hợp tồi nhất O(n) phép chia, trong đó n là số số đầu vào. Độ phức tạp của thuật toán trên thực tế là O(n²). Lý do là, phép chia 2 số n-bit mất O(n(m+1)) thời gian, m là độ dài thương số. Lưu ý rằng việc tính toán UCLN gcd(a,b), a và b là n bit, a₀,…,a_k là thứ tự các số được đưa ra bởi thuật toán và n0,…,nk là độ dài của chúng. Khi k = O(n) và thời gian chạy bị hạn chế bởi:

Điều này tốt hơn nhiều so với thuật toán Euclid cổ điển, phép toán module được thực hiện hiệu quả sử dụng phép trừ lặp với O(2n) bước. Bởi vậy, dạng này của thuật toán yêu cầu O(2nn) thời gian cho số có n số, hoặc O(mlogm) thời gian cho số m. Thuật toán Euclid được sử dụng rộng rãi trên thực tế, đặc biệt với những số nhỏ, do sự đơn giản của nó. Một thuật toán lựa chọn , thuật toán GCD nhị phân (binary GCD algorithm), khai thác sự biểu diễn nhị phân sử dụng cho máy tính để loại bỏ bớt phép chia, và vì thế tăng hiệu suất tính toán.

Có những thuật toán phức tạp hơn có thể giảm thời gian chạy xuống O(n(log_n)²(loglog_n)).

Mối liên quan với continued fractions

Các thương số xuất hiện khi thuật toán Euclid được áp dụng cho các đầu vào a và b là những số xuất hiện hoàn toàn chính xác trong sự biểu diễn liên phân số a/b. Ví dụ a = 1071 và b = 1029 được sử dụng ở trên. Ở đây chỉ tính toán với những thương số thấy rõ nhất:

1071 = 1029 x 1 + 42

1029 = 42 x 24 + 21

42 = 21 x 2 + 0

Theo đó,

Phương thức này áp dụng cho các đầu vào tùy ý a và b (≠ 0), nếu a/b là số vô tỉ thì thuật toán Euclid không kết thúc, nhưng thứ tự tính toán của thương số vẫn biểu diễn liên phân số a/b.

Các thương số 1,24,2 là các hình vuông được lồng vào một hình chữ nhật R có chiều dài là 1071 và chiều rộng là 1029 theo cách sau:

(1) Có 1 hình vuông 1029x1029 trong R đã được cắt xén còn lại hình chữ nhật R1 42x1029

(2) Có 24 hình vuông 42x42 trong R1 đã được cắt xén còn lại hình chữ nhật R2 21x42

(3) Có 2 hình vuông 21x21 trong R2, vừa đủ.

Thuật toán Euclid trực quan “các hình vuông” ứng dụng cho một hình chữ nhật R bất kì. Nếu chiều dài/chiều rộng của R là một số vô tỉ, thì thuật toán Euclid trực quan mở rộng cho một liên phân số trực quan.

Khái quát về phạm vi của thuật toán Euclid

Thuật toán Euclid có thể áp dụng cho các nhóm số khác, không chỉ cho số tự nhiên. Trường hợp cá biệt là các số nguyên Gaussian và các nhóm đa thức. Một ví dụ, xem xét nhóm đa thức với hệ số hữu tỷ. Trong nhóm này, phép chia với phần dư được thực hiện sử dụng phép chia đa thức.

Ta tính UCLN của

x⁴ − 4x³ + 4x² − 3x + 14 = (x² − 5x + 7)(x² + x + 2)

và

x⁴ + 8x³ + 12x² + 17x + 6 = (x² + 7x + 3)(x² + x + 2)

Thuật toán đưa ra các giá trị sau:

------------------------------------------------

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.

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*q
     y:= y0-y1*q
     if r=0 then Break
     a:=b
     b:=r
     x0:=x1     
     x1:=x
     y0:=y1     
     y1:=y
}
   Return d:=b, x, y;

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

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

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.

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*q
     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"

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 .