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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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

Cơ sở lý thuyết của giải thuật[sửa | sửa mã nguồn]

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_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=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<r_2;
....;
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_iy_i sao cho:
a*x_i+b*y_i = r_i với i =0,1,....

Ta có

a*1+b*0= a = r_oa*0+b*1 =b =r_1, nghĩa là
x_o=1,x_1=0y_o=0,y_1=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}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]

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ụ[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 r_i r_{i+1} r_{i+2} q_{i+1} x_i x_{i+1} x_{i+2} y_i y_{i+1} 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=UCLN(29,8)=1x=-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 \mathbb{Z}_m[sửa | sửa mã nguồn]

Số nghịch đảo trong vành \mathbb{Z}_m[sửa | sửa mã nguồn]

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

\mathbb{Z}_m = \left \{ 0,1,...,m-1 \right \}

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

a+b=(a+b) \quad mod \quad m
a*b=(a*b) \quad mod \quad m

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

Đẳ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]

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

Liên kết ngoài[sửa | sửa mã nguồn]