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

Nhập phép tính

Cơ số

Số mũ

Modulo

Kết quả

Kết quả lũy thừa đồng dư

9

7^256 mod 13

Cơ số	7
Số mũ	256
Modulo	13

Máy Tính Lũy Thừa Modulo là gì?

Máy tính lũy thừa modulo dùng để tính (cơ số^{số mũ}) mod m — tức phần dư còn lại sau khi nâng cơ số lên một lũy thừa rồi chia cho modulo. Phép toán này, gọi là lũy thừa đồng dư (modular exponentiation), xuất hiện ở khắp nơi trong lý thuyết số và mật mã học: nó là nền tảng của mã hóa RSA, trao đổi khóa Diffie-Hellman, các phép kiểm tra số nguyên tố và hàm băm. Nếu tính trực tiếp (lấy ra cả lũy thừa khổng lồ trước rồi mới chia lấy dư) thì với số mũ lớn gần như là bất khả thi, vì vậy ta dùng một thuật toán nhanh hơn nhiều.

Cách sử dụng

Nhập ba số nguyên: cơ số, số mũ (bằng 0 hoặc dương) và modulo \(m\) (số nguyên dương lớn hơn 1). Nhấn tính toán, công cụ sẽ trả về kết quả nằm trong khoảng từ 0 đến \(m-1\). Với cơ số âm, máy tính tự động quy về phần dư không âm hợp lệ.

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

Công thức tổng quát là

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

Thay vì dựng nên con số khổng lồ cơ số^{số mũ}, máy tính áp dụng phương pháp bình phương và nhân (còn gọi là lũy thừa nhị phân). Nó đọc số mũ dưới dạng nhị phân. Bắt đầu với kết quả bằng 1, thuật toán liên tục bình phương cơ số theo modulo \(m\); mỗi khi chữ số nhị phân hiện tại của số mũ là 1, nó nhân giá trị bình phương đó vào kết quả đang tính, rồi lại lấy dư theo modulo \(m\). Vì mọi giá trị trung gian luôn nhỏ hơn \(m^2\), phép tính vẫn rất nhanh ngay cả khi số mũ có hàng trăm chữ số.

Quảng cáo

Bình phương và nhân: quét các bit của số mũ, bình phương ở mỗi bước và nhân khi bit bằng 1, luôn lấy modulo \(m\).

Ví dụ minh họa

Tính \(7^{256} \bmod 13\). Bậc của 7 theo modulo 13 là ước của 12, và \(7^{12} \equiv 1\). Vì \(256 = 12 \times 21 + 4\), ta có $$7^{256} \equiv 7^{4} = 2401 \equiv 9 \pmod{13}.$$ Vậy đáp án là 9 — tìm được ngay lập tức tại đây mà không cần dựng nên con số \(7^{256}\) dài tới 217 chữ số.

Mỗi bước bình phương giá trị hiện tại và lấy modulo \(m\), nhân thêm cơ số tại những bit số mũ bằng 1.

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

Nếu modulo bằng 1 thì sao? Mọi số nguyên đều đồng dư với 0 theo modulo 1, nên kết quả luôn là 0.

Số mũ có thể bằng 0 không? Có. Bất kỳ cơ số nào lũy thừa 0 đều bằng 1, nên kết quả là \(1 \bmod m\) (bằng 1 khi \(m > 1\)).

Tại sao không tính lũy thừa trực tiếp luôn? Với số mũ lớn, con số trung gian sẽ có số chữ số khổng lồ và gây tràn số. Việc lấy dư ở từng bước giúp các giá trị luôn nhỏ và thuật toán luôn hiệu quả.