Máy Tính Lũy Thừa Modulo

Nhập phép tính

Cơ số (a)

Số mũ (b)

Modulo (m)

Kết quả

a^b mod m

445

phần dư

Cơ số (a)	4
Số mũ (b)	13
Modulo (m)	497

Lũy thừa modulo là gì?

Lũy thừa modulo dùng để tính \(a^{b} \bmod m\) — phần dư còn lại khi lấy lũy thừa a^b chia cho modulo m. Đây là một trong những phép toán quan trọng bậc nhất trong lý thuyết số và mật mã học, là nền tảng cho các thuật toán như RSA, trao đổi khóa Diffie–Hellman và chữ ký số. Ngay cả khi a^b lớn đến mức khổng lồ, kết quả khi lấy modulo m vẫn nhỏ gọn và tính được dễ dàng.

$$\text{result} = \text{Base } a^{\text{Exponent } b} \bmod \text{Modulus } m$$

Số học mô-đun làm kết quả quay vòng quanh một mô-đun cố định, giống như chiếc đồng hồ.

Cách sử dụng máy tính

Nhập ba số nguyên: cơ số a, số mũ không âm b, và modulo m (một số nguyên dương). Bấm tính và bạn sẽ nhận được phần dư duy nhất nằm trong khoảng từ 0 đến m−1. Cơ số có thể là số âm; trong trường hợp đó, nó sẽ được quy về phần dư hợp lệ trước khi thực hiện lũy thừa.

Giải thích công thức

Tính trực tiếp a^b là điều bất khả thi khi b lớn, nên công cụ này dùng phương pháp bình phương và nhân (còn gọi là lũy thừa nhanh hay lũy thừa nhị phân). Số mũ được đọc dưới dạng nhị phân. Bắt đầu với kết quả r = 1 và cơ số đã rút gọn theo mod m, với mỗi bit của số mũ ta bình phương cơ số (mod m); mỗi khi bit hiện tại là 1, ta nhân kết quả với cơ số (mod m). Cách này chỉ cần khoảng \(\log_2(b)\) phép nhân thay vì b phép nhân.

Quảng cáo

Phương pháp bình phương và nhân xử lý các chữ số nhị phân của số mũ, bình phương ở mỗi bước và nhân khi bit bằng 1.

Ví dụ minh họa

Tính \(4^{13} \bmod 497\). Số mũ 13 trong hệ nhị phân là 1101. Lần lượt theo phương pháp bình phương và nhân: \(4^1 = 4\), \(4^2 = 16\), \(4^4 = 256\), \(4^8 = 256^2 = 65536 \equiv 30 \pmod{497}\). Vì \(13 = 8 + 4 + 1\), ta nhân các lũy thừa tương ứng: $$30 \times 256 \times 4 = 30720 \equiv 445 \pmod{497}$$ Vậy \(4^{13} \bmod 497 = \textbf{445}\).

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

Nếu số mũ bằng 0 thì sao? Bất kỳ số nào lũy thừa 0 đều bằng 1, nên kết quả là \(1 \bmod m\) (bằng 0 khi m = 1).

Cơ số có thể là số âm không? Được. Cơ số âm sẽ được chuyển về phần dư dương tương đương theo mod m trước, nên đáp án luôn nằm trong khoảng từ 0 đến m−1.

Tại sao không tính thẳng a^b rồi lấy mod? Với kích thước dùng trong mật mã, a^b có thể lên tới hàng triệu chữ số. Việc rút gọn mod m ở mỗi bước giúp giữ các con số nhỏ gọn và quá trình tính toán nhanh chóng.