Nguyên tắc thuật toán:
Thuật toán Euclide mở rộng không chỉ tính ước số chung lớn nhất gcd(a, m) của hai số nguyên a và m mà còn tìm các số nguyên x và y sao cho ax + my = gcd(a, m)。
Đây là một ứng dụng của đẳng thức Bézout (phương trình Bézout).
Các bước thuật toán:
- Thuật toán Euclide:Tính gcd(a, m) bằng thuật toán chia, ghi lại thương và số dư ở mỗi bước.
- Thay thế trở lại:Bắt đầu từ bước cuối cùng, thay thế ngược lại để biểu thị từng số dư dưới dạng tổ hợp tuyến tính của a và m.
- Giải hệ số:Cuối cùng, thu được hệ số x và y thỏa mãn ax + my = gcd(a, m).
Nghịch đảo mô-đun:
Khi gcd(a, m) = 1 (tức là a và m nguyên tố cùng nhau), tồn tại một nghịch đảo nhân của modulo m, ký hiệu là a-1mod m. Trong trường hợp này, x là nghịch đảo mô đun, thỏa mãn a × x ≡ 1 (mod m)。
Nếu x âm thì cần điều chỉnh về giá trị dương: x' = x mod m.
Ứng dụng:
- Mật mã:Tính toán khóa riêng trong thuật toán RSA yêu cầu tìm nghịch đảo mô-đun.
- Các vấn đề lý thuyết số:Giải các đồng dư tuyến tính dạng ax ≡ b (mod m).
- Tổ hợp:Tính toán tổ hợp mô-đun (Định lý Lucas, v.v.)
- Lập trình cạnh tranh:Tính toán nghịch đảo mô-đun nhanh để tránh các vấn đề về độ chính xác từ phép chia
Độ phức tạp về thời gian:
O(log min(a, m)), Giống như Thuật toán Euclide
Danh tính của Bézout:
Với mọi số nguyên a và m, tồn tại các số nguyên x và y sao cho ax + my = gcd(a, m). Các hệ số x và y này có thể được tính toán một cách hiệu quả bằng Thuật toán Euclide mở rộng.