Máy tính Thuật toán Euclid Mở rộng

Máy tính Thuật toán Euclid mở rộng tính Ước chung lớn nhất (GCD) của hai số nguyên và tìm các hệ số Bézout — các số nguyên s và t thỏa mãn gcd(a, b) = s·a + t·b. Ngoài việc tính GCD, công cụ này còn cung cấp bảng chia từng bước hoàn toàn tự động, thế ngược và tính nghịch đảo modulo, lý tưởng cho các khóa học lý thuyết số, nghiên cứu mật mã và lập trình thi đấu.

Thuật toán Euclid mở rộng là gì?

Thuật toán Euclid mở rộng (EEA) là một phần mở rộng của thuật toán Euclid tìm GCD cổ điển. Trong khi thuật toán cơ bản tìm gcd(a, b) bằng cách chia liên tiếp, phiên bản mở rộng đồng thời theo dõi hai dãy số nguyên ghi lại cách mỗi số dư có thể được biểu diễn dưới dạng tổ hợp tuyến tính của các đầu vào ban đầu.

Cách thuật toán hoạt động

EEA duy trì ba cặp giá trị — (r, s, t) — qua mỗi bước chia:

1. Khởi tạo: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Mỗi bước: tính thương số q = ⌊rₙ₋₁ / rₙ⌋, sau đó cập nhật rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Dừng lại khi số dư = 0; số dư trước đó là gcd(a, b)
4. Các giá trị s và t tương ứng là các hệ số Bézout

Ví dụ từng bước: gcd(252, 105)

Kết quả: gcd(252, 105) = 21, với đồng nhất thức Bézout: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Hãy tự mình thử với máy tính ở trên để có các hệ số chính xác.

Ứng dụng của Thuật toán Euclid mở rộng

1. Nghịch đảo modulo (Mật mã học)

Ứng dụng quan trọng nhất là tính nghịch đảo modulo. Nếu gcd(a, m) = 1, thì hệ số Bézout s thỏa mãn:

Nghịch đảo modulo là thiết yếu trong mã hóa RSA (tính số mũ khóa bí mật d), trao đổi khóa Diffie-Hellman và mật mã đường cong elliptic.

2. Giải phương trình Diophantine tuyến tính

Phương trình ax + by = c có nghiệm nguyên khi và chỉ khi gcd(a, b) chia hết c. Nếu vậy, một nghiệm cụ thể là x₀ = s·(c/d), y₀ = t·(c/d) trong đó d = gcd(a, b) và s, t là các hệ số Bézout.

3. Định lý số dư Trung Hoa

EEA được sử dụng trong chứng minh kiến tạo và tính toán Định lý số dư Trung Hoa — tìm x sao cho x ≡ a₁ (mod m₁) và x ≡ a₂ (mod m₂) — bằng cách tính nghịch đảo modulo của các mô-đun.

4. Rút gọn phân số và LCD

gcd(a, b) = 1 xác nhận rằng a/b đã ở dạng tối giản. BCNN là lcm(a, b) = |a·b| / gcd(a, b).

Các hệ số Bézout không phải là duy nhất

Các hệ số Bézout s và t không phải là duy nhất. Nếu (s, t) là một nghiệm, thì (s + k·(b/d), t − k·(a/d)) cũng là một nghiệm cho bất kỳ số nguyên k nào, trong đó d = gcd(a, b). EEA trả về nghiệm mà |s| ≤ |b/d| và |t| ≤ |a/d|.

Độ phức tạp thời gian

Thuật toán Euclid mở rộng chạy trong O(log min(a, b)) lần lặp — tương tự như thuật toán Euclid cơ bản. Theo định lý Lamé, số bước không bao giờ vượt quá 5 lần số chữ số thập phân của số đầu vào nhỏ hơn. Điều này làm cho nó cực kỳ hiệu quả ngay cả đối với các số nguyên lớn được sử dụng trong các ứng dụng mật mã.

Câu hỏi thường gặp

Thuật toán Euclid mở rộng là gì?

Thuật toán Euclid mở rộng là bản mở rộng của thuật toán GCD của Euclid để tính thêm các hệ số Bézout s và t thỏa mãn gcd(a, b) = s·a + t·b. Nó theo dõi cách mỗi số dư có thể được biểu diễn dưới dạng tổ hợp tuyến tính của a và b trong suốt quá trình chia.

Hệ số Bézout là gì?

Hệ số Bézout là các số nguyên s và t được đảm bảo tồn tại bởi đồng nhất thức Bézout (một định lý trong lý thuyết số). Chúng thỏa mãn gcd(a, b) = s·a + t·b và được tính toán hiệu quả bởi Thuật toán Euclid mở rộng. Chúng được sử dụng trong tính nghịch đảo modulo, giải phương trình Diophantine và Định lý số dư Trung Hoa.

Làm thế nào để tìm nghịch đảo modulo bằng Thuật toán Euclid mở rộng?

Nếu gcd(a, b) = 1 (a và b nguyên tố cùng nhau), hệ số Bézout s thỏa mãn s·a ≡ 1 (mod b). Nghịch đảo modulo của a mod b là s mod b (được điều chỉnh để dương). Máy tính này hiển thị trực tiếp điều này trong kết quả.

Khi nào nghịch đảo modulo không tồn tại?

Nghịch đảo modulo của a theo mô-đun m tồn tại khi và chỉ khi gcd(a, m) = 1. Nếu gcd(a, m) > 1, không có số nguyên x nào thỏa mãn a·x ≡ 1 (mod m).

Độ phức tạp thời gian của Thuật toán Euclid mở rộng là bao nhiêu?

O(log min(a, b)) phép chia, tương tự như thuật toán Euclid cơ bản. Theo định lý Lamé, số bước bị giới hạn bởi 5 lần số chữ số thập phân của số đầu vào nhỏ hơn, giúp nó hoạt động rất hiệu quả.

Tài nguyên bổ sung

• Thuật toán Euclid mở rộng - Wikipedia
• Đồng nhất thức Bézout - Wikipedia
• Phần tử nghịch đảo modulo - Wikipedia