Bài 4: Giải Thuật Euclid Và Euclid Mở Rộng - Blog Nam Phạm
Có thể bạn quan tâ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.
- Thuật toán Euclid tìm ƯCLN
- Thuật toán
- Ví dụ
- Chương trình
- Bài tập
- Thuật toán Euclid mở rộng
- Cơ sở lý thuyết của giải thuật
- Giải thuật
- Chương trình
- Ví dụ
- Bài tập
- Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành ZN
- Chương trình
- Ví dụ
- Bài tập
- Cơ sở lý thuyết của giải thuật
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 aDạ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:
- Tìm GCD(973, 301)
- Tìm GCD(1970, 1066)
- Tìm GCD(4864, 3458)
- Tìm GCD(42823, 6409)
- 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 SubTham 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}$
- Khởi tạo:
- ${\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.
- Lấy lại các kết quả trê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 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
- Cho a=973, b=301. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)
- Cho a=1970, b=1066. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)
- Cho a=42823, b=6409. Tìm x, y và GCD(a, b) thoản mãn ax + by = d = GCD(a,b)
- 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}$
- Khởi tạo:
- ${\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}$
- Lấy lại các giá trị:
- 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}$
- Lấy lại các giá trị:
- ${\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.
- Các giá trị:
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
- Tính r1-1 mod r0 với r0=101, r1=25
- Tính r1-1 mod r0 với r0=11, r1=60
- Tính r1-1 mod r0 với r0=1024, r1=173
- Tính r1-1 mod r0 với r0=323, r1=299
- Tính r1-1 mod r0 với r0=460, r1=3
- Tính 5/6 mod 7
- Tính 15-1 mod 101
- Tính 41-1 mod 100
- Tính (235*126/13) mod 19
- 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
Từ khóa » Thuật Toán ơ Cơ Lít
-
Giải Thuật Euclid – Wikipedia Tiếng Việt
-
Tìm UCLN (174,18) Bằng Thuật Toán Ơclit - Nguyễn Hạ Lan - HOC247
-
Lý Thuyết Số Về Thuật Toán Oclit - TaiLieu.VN
-
Áp Dụng Thuật Toán Ơ-clit để Tìm ƯCLN Của: 126 Và 162 - Haylamdo
-
Tìm UCLN Của Hai Số Bằng Thuật Toán Ơclit - YouTube
-
Thuật Toán Euclid
-
THUẬT TOÁN ƠCLIT TÌM ƯCLN, BCNN - Tài Liệu Text - 123doc
-
Áp Dụng Thuật Toán Euclid Tính Nhanh ước Chung Lớn Nhất & Bội Số ...
-
Tìm Ucln Của Hai Số Bằng Thuật Toán Ơ Cơ Lít, Giải Thuật Euclid
-
Thuật Toán ơ-clit | Cộng đồng Học Sinh Việt Nam - HOCMAI Forum
-
Thuật Toán Euclide Mở Rộng - VNOI
-
Dùng Thuật Toán ơ Cờ Lít để Tìm A, ƯCLN Của 318 Và 214 B ... - Olm