Giải Thuật Euclid Mở Rộng – Wikipedia Tiếng Việt

Bài viết này cần thêm liên kết tới các bài bách khoa khác để trở thành một phần của bách khoa toàn thư trực tuyến Wikipedia. Xin hãy giúp cải thiện bài viết này bằng cách thêm các liên kết có liên quan đến ngữ cảnh trong văn bản hiện tại. (Tìm hiểu cách thức và thời điểm xóa thông báo này)

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

a x + b y = c {\displaystyle ax+by=c}

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

Nếu d = U C L N ( a , b ) {\displaystyle d=UCLN(a,b)} thì tồn tại các số nguyên x , y {\displaystyle x,y} sao cho a x + b y = d {\displaystyle ax+by=d}

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

[sửa | sửa mã nguồn]

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 {\displaystyle r_{o}=a,r_{1}=b} , chia r 0 {\displaystyle r_{0}} cho r 1 {\displaystyle r_{1}} được số dư r 2 {\displaystyle r_{2}} và thương số nguyên q 1 {\displaystyle q_{1}} . Nếu r 2 = 0 {\displaystyle r_{2}=0} thì dừng, nếu r 2 {\displaystyle r_{2}} khác không, chia r 1 {\displaystyle r_{1}} cho r 2 {\displaystyle r_{2}} được số dư r 3 {\displaystyle r_{3}} ,...Vì dãy các r i {\displaystyle 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 {\displaystyle r_{m+2}=0} .

r o = q 1 ∗ r 1 + r 2 , 0 < r 2 < r 1 {\displaystyle 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 {\displaystyle 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 {\displaystyle r_{m-1}=q_{m}*r_{m}+r_{m+1},0<r_{m+1}<r_{m}} r m = q m + 1 ∗ r m + 1 {\displaystyle r_{m}=q_{m+1}*r_{m+1}}

trong đó số dư cuối cùng khác 0 là r m + 1 = d {\displaystyle 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 ) {\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

x i {\displaystyle x_{i}} và y i {\displaystyle y_{i}} sao cho: a ∗ x i + b ∗ y i = r i {\displaystyle a*x_{i}+b*y_{i}=r_{i}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} .

Ta có

a ∗ 1 + b ∗ 0 = a = r o {\displaystyle a*1+b*0=a=r_{o}} và a ∗ 0 + b ∗ 1 = b = r 1 {\displaystyle a*0+b*1=b=r_{1}} , nghĩa là x o = 1 , x 1 = 0 {\displaystyle x_{o}=1,x_{1}=0} và y o = 0 , y 1 = 1 {\displaystyle y_{o}=0,y_{1}=1} . (1)

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

a ∗ x i + b ∗ y i = r i {\displaystyle a*x_{i}+b*y_{i}=r_{i}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} . a ∗ x i + 1 + b ∗ y i + 1 = r i + 1 {\displaystyle a*x_{i+1}+b*y_{i+1}=r_{i+1}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} .

Khi đó từ

r i = q i + 1 ∗ r i + 1 + r i + 2 {\displaystyle r_{i}=q_{i+1}*r_{i+1}+r_{i+2}}

suy ra

r i − q i + 1 ∗ r i + 1 = r i + 2 {\displaystyle 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 {\displaystyle (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 {\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

x i + 2 = x i − q i + 1 ∗ x i + 1 {\displaystyle x_{i+2}=x_{i}-q_{i+1}*x_{i+1}} (2) y i + 2 = y i − q i + 1 ∗ y i + 1 {\displaystyle y_{i+2}=y_{i}-q_{i+1}*y_{i+1}} (3)

Khi i = m − 1 {\displaystyle i=m-1} ta có được x m + 1 {\displaystyle x_{m+1}} và y m + 1 {\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

[sửa | sửa mã nguồn] {Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)} functiongcd(a,b); begin whileb≠0do begin r:=amodb;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.} functionExtended_gcd(a,b); begin (xa,ya):=(1,0); (xb,yb):=(0,1); whileb≠0do begin q:=adivb; r:=amodb;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ã:

SubEuclid_Extended(a,b) Dimx0,x,y,y1AsSingle x0=1:x1=0:y0=0:y1=1 Whileb>0 r=amodb ifr=0thenExitWhile 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.Printd:=b,x,y code EndSub

Ví dụ

[sửa | sửa mã nguồn]

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

Bước i {\displaystyle i}	r i {\displaystyle r_{i}}	r i + 1 {\displaystyle r_{i+1}}	r i + 2 {\displaystyle r_{i+2}}	q i + 1 {\displaystyle q_{i+1}}	x i {\displaystyle x_{i}}	x i + 1 {\displaystyle x_{i+1}}	x i + 2 {\displaystyle x_{i+2}}	y i {\displaystyle y_{i}}	y i + 1 {\displaystyle y_{i+1}}	y i + 2 {\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 d = U C L N ( 29 , 8 ) = 1 {\displaystyle d=UCLN(29,8)=1} và x = − 3 {\displaystyle x=-3} , y = 11 {\displaystyle y=11} . Dễ dàng kiểm tra hệ thức 29 ∗ ( − 3 ) + 8 ∗ 11 = 1 {\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 Z m {\displaystyle \mathbb {Z} _{m}}

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

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

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

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

a + b = ( a + b ) m o d m {\displaystyle a+b=(a+b)\quad mod\quad m} a ∗ b = ( a ∗ b ) m o d m {\displaystyle a*b=(a*b)\quad mod\quad m}

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

m ∗ x + a ∗ y = 1 {\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

[sửa | sửa mã nguồn] //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 functionModuloInverse(a,m); begin xa:=1;xm:=0; whilem≠0do begin q:=adivm; xr:=xa-q*xm; xa:=xm; xm:=xr; r:=amodm; 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ụ

[sửa | sửa mã nguồn]

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 {\displaystyle -37} . Lấy số đối của 37 {\displaystyle 37} theo mođun 101 {\displaystyle 101} được 64 {\displaystyle 64} . Vậy 30 − 1 m o d 101 = 64 {\displaystyle 30^{-1}\,mod\,101=64} .

Ứng dụng

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

• Giải thuật Euclid

Tham khảo

[sửa | sửa mã nguồn]

Liên kết ngoài

[sửa | sửa mã nguồn]

• 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