Bài 4: Giải Thuật Euclid Và Euclid Mở Rộng - Blog Nam Phạm

Trong toán học, giải thuật Euclid (hay thuật toán Euclid) là một giải thuật để tính ước chung lớn nhất (ƯCLN) của hai số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với số dư bằng không. Giải thuật này được đặt tên theo nhà toán học người Hy Lạp cổ đại Euclid.

1. Thuật toán Euclid tìm ƯCLN
   1. Thuật toán
   2. Ví dụ
   3. Chương trình
   4. Bài tập
2. Thuật toán Euclid mở rộng
   1. Cơ sở lý thuyết của giải thuật
      1. Giải thuật
      2. Chương trình
      3. Ví dụ
      4. Bài tập
   2. Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành ZN
      1. Chương trình
      2. Ví dụ
      3. Bài tập

Thuật toán Euclid tìm ƯCLN

Thuật toán

Thuật toán Euclid dùng để tìm ước số chung lớn nhất của hai số nguyên a và b. Ta ký hiệu ước số chung lớn nhất này là gcd(a, b). Thuật toán này dựa trên định lý sau:

Định lý: với mọi số nguyên a ≥ 0 và b > 0 thì:

gcd(a, b) = gcd(b, a mod b)

Nếu ƯCLN(a, b) = 1 thì a và b được gọi là hai số nguyên tố cùng nhau (đã được đề cập trong bài trước). Tính chất này không khẳng định a và b là số nguyên tố. Chẳng hạn, 6 và 35 đều không phải là số nguyên tố vì chúng đều có thể được phân tích thành tích của các thừa số nguyên tố: 6 = 2 × 3 và 35 = 5 × 7. Tuy nhiên, 6 và 35 nguyên tố cùng nhau vì chúng không có một thừa số chung nào.

Xem thêm: https://vi.wikipedia.org/wiki/Giải_thuật_Euclid

Ví dụ

Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta trừ bội của 462 từ 1071 thì được thương q0 = 2 và số dư là 147:

1071 = 2 × 462 + 147.

Tiếp tục trừ bội của 147 từ 462 thì được thương q1 = 3 và số dư là 21:

462 = 3 × 147 + 21.

Tiếp tục trừ bội của 21 từ 147 thì được thương q2 = 7 và số dư là 0:

147 = 7 × 21 + 0.

Vì số dư cuối cùng bằng 0 nên thuật toán kết thúc với 21 là ƯCLN của 1071 và 462, bằng với ƯCLN có được từ phép phân tích ra thừa số nguyên tố như trên. Các bước được tóm tắt thành bảng sau:

Bước k	Phương trình	Thương và số dư
0	1071 = q0 462 + r0	q0 = 2 và r0 = 147
1	462 = q1 147 + r1	q1 = 3 và r1 = 21
2	147 = q2 21 + r2	q2 = 7 và r2 = 0; kết thúc

Chương trình

Giải thuật Euclid có thể được biểu diễn bằng mã giả. Chẳng hạn, dạng phép chia của nó có thể được lập trình như sau:

function gcd(a, b) while a ≠ b if a > b a:= a − b else b:= b − a return a

Dạng đệ quy dựa trên tính chất ƯCLN của các cặp số dư liên tiếp là bằng nhau và điều kiện dừng lại là ${\displaystyle GCD(r_{N-1},0)=r_{N-1}}$ .

function gcd(a, b) if b = 0 return a else return gcd(b, a mod b)

Code tính WCLN bằng C/C++, Java, C#, PHP, Python, Javascript mọi người có thể tham khảo link này: https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/

Bài tập

Dùng thuật toán Euclid:

1. Tìm GCD(973, 301)
2. Tìm GCD(1970, 1066)
3. Tìm GCD(4864, 3458)
4. Tìm GCD(42823, 6409)
5. Tìm GCD(91470, 51066)

Thuật toán 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:

$${\displaystyle ax+by=c}$$

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

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

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

Giải thuật

Giải thuật Euclid mở rộng kết hợp quá trình tìm GCD(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 ${\displaystyle r_{o}=a,r_{1}=b}$, chia ${\displaystyle r_{0}}$ cho ${\displaystyle r_{1}}$ được số dư ${\displaystyle r_{2}}$ và thương số nguyên ${\displaystyle q_{1}}$. Nếu ${\displaystyle r_{2}=0}$ thì dừng, nếu ${\displaystyle r_{2}}$ khác không, chia ${\displaystyle r_{1}}$ cho ${\displaystyle r_{2}}$ được số dư ${\displaystyle r_{3}}$,…Vì dãy các ${\displaystyle r_{i}}$ là giảm thực sự nên sau hữu hạn bước ta được số dư ${\displaystyle r_{m+2}=0}$.

${\displaystyle r_{o}=q_{1}*r_{1}+r_{2},0<r_{2}<r_{1}}$;

${\displaystyle r_{1}=q_{2}*r_{2}+r_{3},0<r_{3}<r_{2}}$;

….;

${\displaystyle r_{m-1}=q_{m}r_{m}+r_{m+1},0r_{m+1}}$

${\displaystyle r_{m}=q_{m+1}*r_{m+1}}$

trong đó số dư cuối cùng khác 0 là ${\displaystyle r_{m+1}=d}$. Bài toán đặt ra là tìm x, y sao cho $${\displaystyle ax+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 ${\displaystyle x_{i}}$ và ${\displaystyle y_{i}}$ sao cho:${\displaystyle ax_{i}+by_{i}=r_{i}}$ với ${\displaystyle i=0,1,…}$.

Ta có: ${\displaystyle a_{1}+b_{0}=a=r_{0}}$ và ${\displaystyle a_{0}+b_{1}=b=r_{1}}$, nghĩa là ${\displaystyle x_{0}=1,x_{1}=0}$ và ${\displaystyle y_{0}=0,y_{1}=1}$. (1)

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

${\displaystyle ax_{i}+by_{i}=r_{i}}$ với ${\displaystyle i=0,1,…}$.${\displaystyle ax_{i+1}+by_{i+1}=r_{i+1}}$ với ${\displaystyle i=0,1,…}$.

Khi đó từ ${\displaystyle r_{i}=q_{i+1}r_{i+1}+r_{i+2}}$ suy ra

$${\displaystyle r_{i}-q_{i+1}r_{i+1}=r_{i+2}}$$ $${\displaystyle (ax_{i}+by_{i})-q_{i+1}(ax_{i+1}+by_{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

${\displaystyle x_{i+2}=x_{i}-q_{i+1}x_{i+1}}$ (2)

${\displaystyle y_{i+2}=y_{i}-q_{i+1}y_{i+1}}$ (3)

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

Chương trình

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-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

Tham khảo code thuật toán Euclid và Euclid mở rộng trong trang sau: https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/

Ví dụ

Với a=29, b=8. Tìm x,y và d thoản mãn ax + by = d = GCD(a,b)

• ${\displaystyle i=0}$
  • Khởi tạo:
    • ${\displaystyle r_{i}=r_{0}=a=29}$, ${\displaystyle r_{i+1}=r_{1}=b=8}$,
    • ${\displaystyle x_{i}=x_{0}=1}$ và ${\displaystyle x_{1}=0}$,
    • ${\displaystyle y_{i}=y_{0}=0}$ và ${\displaystyle y_{1}=1}$
  • Tính:
    • ${\displaystyle r_{i}:r_{i+1} = r_{0}:r_{1}}$ = 29 chia 8 được 3 dư 5 => ${\displaystyle r_{i+2}=r_{2}=5}$, ${\displaystyle q_{i+1}=q_{1}=3}$
    • ${\displaystyle x_{i+2}=x_{2}=x_{i}-q_{i+1}x_{i+1}=x_{0}-q_{1}x_{1}=1-3*0=1}$
    • ${\displaystyle y_{i+2}=y_{2}=y_{i}-q_{i+1}y_{i+1}=y_{0}-q_{1}y_{1}=0-3*1=-3}$
• ${\displaystyle i=1}$
  • Lấy lại các kết quả trên:
    • ${\displaystyle r_{i}=r_{1}=8}$, ${\displaystyle r_{i+1}=r_{2}=5}$
    • ${\displaystyle x_{i}=x_{1}=0}$, ${\displaystyle x_{i+1}=x_{2}=1}$
    • ${\displaystyle y_{i}=y_{1}=1}$, ${\displaystyle y_{i+1}=y_{2}=-3}$
  • Tính:
    • ${\displaystyle r_{i}:r_{i+1}=r_{1}:r_{2}=8:5}$ được 1 dư 3 => ${\displaystyle r_{i+2}=r_{3}=3}$, ${\displaystyle q_{i+1}=q_{2}=1}$
    • ${\displaystyle x_{i+2}=x_{3}=x_{i}-q_{i+1}x_{i+1}=x_{1}-q_{2}x_{2}=0-1*1=-1}$
    • ${\displaystyle y_{i+2}=y_{3}=y_{i}-q_{i+1}y_{i+1}=y_{1}-q_{2}y_{2}=1-1*(-3)=-4}$
  • Tương tự với ${\displaystyle i=2}$, ${\displaystyle i=3}$
    • ${\displaystyle r_{i}=q_{i+1}r_{i+1}+r_{i+2}}$
    • ${\displaystyle x_{i+2}=x_{i}-q_{i+1}x_{i+1}}$
    • ${\displaystyle y_{i+2}=y_{i}-q_{i+1}y_{i+1}}$
  • ${\displaystyle i=4}$
    • ${\displaystyle r_{i}:r_{i+1}=r_{4}:r_{5}=2:1}$ được 2 dư 0 => ${\displaystyle r_{i+2}=r_{6}=0}$, ${\displaystyle q_{i+1}=q_{5}=2}$
    • Do ${\displaystyle r_{i+2}=0}$ thuật toán kết thúc.

Giải thuật trải qua các bước được mô tả qua bảng dưới đây:

Bước ${\displaystyle i}$	${\displaystyle r_{i}}$	${\displaystyle r_{i+1}}$	${\displaystyle r_{i+2}}$	${\displaystyle q_{i+1}}$	${\displaystyle x_{i}}$	${\displaystyle x_{i+1}}$	${\displaystyle x_{i+2}}$	${\displaystyle y_{i}}$	${\displaystyle y_{i+1}}$	${\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 ${\displaystyle d=GCD(29,8)=r_{i+1}=r_{5}=1}$ và ${\displaystyle x=x_{i+2}=x_{5}=-3}$, ${\displaystyle y=y_{i+2}=y_{5}=11}$. Dễ dàng kiểm tra hệ thức ${\displaystyle a*x+b*y=29(-3)+8*11=d=GCD(a,b)=1}$ (i=4)

Bài tập

1. Cho a=973, b=301. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)
2. Cho a=1970, b=1066. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)
3. Cho a=42823, b=6409. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)
4. Cho a=91470, b=51066. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)

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

Ở bài trước ta đã đề cập đến phần tử nghịch đảo của một số trong vành ZN. Định lý về sự tồn tại của phần tử nghịch đảo: Nếu GCD(a, N) = 1 thì tồn tại duy nhất 1 số b ∈ ZN là phần tử nghịch đảo của a, nghĩa là thoả mãn a.b = (a*b) mod N ≡ 1 (mod N).

Trong lý thuyết số đã chứng minh rằng, số a là khả nghịch theo modulo m khi và chỉ khi GCD của a và m bằng 1. Khi đó tồn tại các số nguyên x và y thoả mãn: $${\displaystyle Nx+ay=1}$$

Đẳng thức này lại chỉ ra y là nghịch đảo của a theo modulo N (y chính là số b thoả mãn a.b=1 theo mod N). Do đó có thể tìm được phần tử nghịch đảo của a theo modulo N nhờ thuật toán Euclid mở rộng khi chia N cho a.

Bây giờ bài toán tính ${\displaystyle a^{-1}\,mod\,N}$ trở thành tìm y sao cho ${\displaystyle Nx+ay=GCD(N, a)=1}$ theo giải thuật Euclid.

Chương trình

Giải thuật tính ${\displaystyle a^{-1}\,mod\,n}$ sau chỉ thực hiện với các số nguyên n>a>0, chương trình viết bằng ngôn ngữ C:

#include <stdio.h> /* Extended Euclidean algorithm for computing multiplicative inverses in modular structures */ long ModuloInverse(long a, long n) // a^-1 mod n { long r, q, y, y0 = 0, y1 = 1, tmp=n; while(a > 0) { r = n % a; q = n / a; if(r == 0) break; y = y0 - y1 * q; n = a; a = r; y0 = y1; y1 = y; } if(a > 1) return -1; // GCD(a,n) # 1 if(y>=0) return y; //a^-1 mod n = y mod n else return y+tmp; //a^-1 mod n = -y mod n = y+n mod n } int main() { printf("%ld^-1 mod %ld = %ld\n", (long)30, (long)101, ModuloInverse(30,101)); //30^-1 mod 101 = 64 return 0; }

Ví dụ

Tính ${\displaystyle 30^{-1}\,mod\,101}$

• ${\displaystyle i=0}$
  • Khởi tạo:
    • ${\displaystyle r_{i}=r_{0}=101}$, ${\displaystyle r{i+1}=r_{1}=30}$
    • ${\displaystyle y_{i}=y_{0}=0}$, ${\displaystyle y_{i+1}=y_{1}=1}$
  • Tính:
    • ${\displaystyle r_{i+2}=r_{i} \% r_{i+1}}$ => ${\displaystyle r_{2}=r_{0} \% r_{1}=101\%30=11}$
    • ${\displaystyle q_{i+1}=r_{i}:r_{i+1}}$ => ${\displaystyle q_{1}=r_{0}:r_{1}=101:30=3}$
    • ${\displaystyle y=y_{i}-y_{i+1}*q_{i+1}}$ => ${\displaystyle y=y_{0}-y_{1}*q_{1}=0-1*3=-3}$
• ${\displaystyle i=1}$
  • Lấy lại các giá trị:
    • ${\displaystyle r_{i}=r_{1}=30}$, ${\displaystyle r{i+1}=r_{2}=11}$
    • ${\displaystyle y_{i}=y_{1}=1}$, ${\displaystyle y_{i+1}=y_{2}=y=-3}$
  • Tính:
    • ${\displaystyle r_{i+2}=r_{i}\%r_{i+1}}$ => ${\displaystyle r_{3}=r_{1}\%r_{2}=30\%11=8}$
    • ${\displaystyle q_{i+1}=r_{i}:r_{i+1}}$ => ${\displaystyle q_{2}=r_{1}:r_{2}=30:11=2}$
    • ${\displaystyle y=y_{i}-y_{i+1}*q_{i+1}}$ => ${\displaystyle y=y_{1}-y_{2}*q_{2}=1-(-3)*2=7}$
• Tương tự với ${\displaystyle i=2, 3}$
• ${\displaystyle i=4}$
  • Lấy lại các giá trị:
    • ${\displaystyle r_{i}=r_{4}=3}$, ${\displaystyle r{i+1}=r_{5}=2}$
    • ${\displaystyle y_{i}=y_{4}=-10}$, ${\displaystyle y_{i+1}=y_{5}=y=27}$
  • Tính:
    • ${\displaystyle r_{i+2}=r_{i}\%r_{i+1}}$ => ${\displaystyle r_{6}=r_{4}\%r_{5}=3\%2=1}$
    • ${\displaystyle q_{i+1}=r_{i}:r_{i+1}}$ => ${\displaystyle q_{5}=r_{4}:r_{5}=3:2=1}$
    • ${\displaystyle y=y_{i}-y_{i+1}*q_{i+1}}$ => ${\displaystyle y=y_{4}-y_{5}*q_{5}=-10-27*1=-37}$
• ${\displaystyle i=5}$
  • Các giá trị:
    • ${\displaystyle r_{i}=r_{5}=2}$, ${\displaystyle r{i+1}=r_{6}=1}$
    • ${\displaystyle y_{i}=y_{5}=27}$, ${\displaystyle y_{i+1}=y_{6}=y=-37}$
  • Tính:
    • ${\displaystyle r_{i+2}=r_{i}\%r_{i+1}}$ => ${\displaystyle r_{7}=r_{5}\%r_{6}=2\%1=0}$
    • ${\displaystyle q_{i+1}=r_{i}:r_{i+1}}$ => ${\displaystyle q_{6}=r_{5}:r_{6}=2:1=2}$
    • Vì ${\displaystyle r_{7}=0}$. Kết thúc thuật toán.

Giải thuật trải qua các bước được mô tả qua bảng dưới đây:

Bước ${\displaystyle i}$	${\displaystyle r_{i}}$	${\displaystyle r_{i+1}}$	${\displaystyle r_{i+2}}$	${\displaystyle q_{i+1}}$	${\displaystyle y_{i}}$	${\displaystyle y_{i+1}}$	${\displaystyle 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	.	.	.	.

Bài tập

1. Tính r1-1 mod r0 với r0=101, r1=25
2. Tính r1-1 mod r0 với r0=11, r1=60
3. Tính r1-1 mod r0 với r0=1024, r1=173
4. Tính r1-1 mod r0 với r0=323, r1=299
5. Tính r1-1 mod r0 với r0=460, r1=3
6. Tính 5/6 mod 7
7. Tính 15-1 mod 101
8. Tính 41-1 mod 100
9. Tính (235*126/13) mod 19
10. Tính (23525/17 + 12619. 397/13) mod 29

Tài liệu tham khảo:

• [1] Phụ lục 2, Bài giảng An toàn và bảo mật thông tin, Đại học Nha Trang.
• [2] https://vi.wikipedia.org/wiki/Giải_thuật_Euclid
• [3] https://vi.wikipedia.org/wiki/Giải_thuật_Euclid_mở_rộng