Máy tính Nghịch đảo Nhân theo Mô-đun

Nghịch đảo nhân theo mô-đun là gì?

Nghịch đảo nhân theo mô-đun của một số nguyên a đối với mô-đun m là một số nguyên x trong phạm vi [0, m-1] sao cho:

Nó được viết là a⁻¹ (mod m) và tương tự như nghịch đảo nhân trong số học thông thường (tức là 1/a), nhưng trong thế giới của số học mô-đun.

Điều kiện then chốt: Nghịch đảo tồn tại khi và chỉ khi gcd(a, m) = 1 — nghĩa là, a và m phải là các số nguyên tố cùng nhau.

Cách tính: Thuật toán Euclid mở rộng

Phương pháp hiệu quả nhất sử dụng Thuật toán Euclid mở rộng. Nó tìm các số nguyên x và y thỏa mãn đẳng thức Bézout:

Khi gcd(a, m) = 1, lấy mô-đun m cả hai vế ta được a·x ≡ 1 (mod m), do đó x là nghịch đảo mô-đun.

Ví dụ: Tìm 3⁻¹ (mod 7):

GCD mở rộng cho: 3·(5) + 7·(-2) = 15 − 14 = 1, vậy 3⁻¹ ≡ 5 (mod 7). Xác minh: 3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

Ứng dụng trong Mật mã học & Toán học

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