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

Tính lũy thừa modular a^b mod n hiệu quả bằng thuật toán lũy thừa nhị phân (lũy thừa nhanh). Nhập cơ số, số mũ và mô-đun để nhận kết quả tức thì với phân tích chi tiết từng bước của phương pháp bình phương và nhân, trực quan hóa phân rã nhị phân và ngữ cảnh mã hóa.

Embed Máy Tính Lũy Thừa Modular Widget

Giới thiệu về Máy Tính Lũy Thừa Modular

Máy tính Lũy thừa Modular tính toán \(a^b \bmod n\) — nâng cơ số \(a\) lên số mũ \(b\) và lấy số dư khi chia cho modulo \(n\). Nó sử dụng thuật toán lũy thừa nhị phân (còn được gọi là lũy thừa nhanh hoặc bình phương và nhân), giúp giảm thiểu phép toán từ \(O(b)\) phép nhân xuống chỉ còn \(O(\log b)\). Đây cũng chính là thuật toán được sử dụng trong các hệ thống mật mã thực tế như RSA, Diffie-Hellman và ElGamal.

Ứng dụng của Lũy thừa Modular

🔐

Mã hóa RSA

Mã hóa và giải mã thông điệp bằng lũy thừa modular với các tích số nguyên tố lớn

🤝

Diffie-Hellman

Giao thức trao đổi khóa tính toán g^a mod p để bảo mật bí mật chung

✍

Chữ ký số

DSA, ECDSA và EdDSA đều dựa trên lũy thừa modular

🧪

Kiểm tra số nguyên tố

Các phép kiểm tra Fermat và Miller-Rabin sử dụng a^(n-1) mod n để kiểm tra tính nguyên tố

🏆

Lập trình thi đấu

Số học modular với lũy thừa nhanh là điều cần thiết cho các bài toán thi đấu

🔗

Blockchain

Bằng chứng công việc (PoW) và băm mật mã dựa trên số học modular

Thuật toán Lũy thừa nhị phân hoạt động như thế nào

Ý tưởng then chốt là chúng ta có thể phân tách bất kỳ số mũ nào thành tổng các lũy thừa của 2 bằng cách sử dụng biểu diễn nhị phân của nó. Ví dụ, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), vì vậy \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

Thuật toán xử lý các chữ số nhị phân của số mũ từ trái sang phải:

Bước 1: Chuyển đổi số mũ \(b\) sang hệ nhị phân.

Bước 2: Khởi tạo kết quả = 1 (hoặc = cơ số nếu bit đầu tiên là 1).

Bước 3: Đối với mỗi bit tiếp theo: Bình phương kết quả (theo mod n). Nếu bit là 1, cũng thực hiện nhân với cơ số (theo mod n).

Bước 4: Sau khi tất cả các bit được xử lý, kết quả là \(a^b \bmod n\).

Mã giả

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // bit là 1
            result = (result × base) mod mod
        exp = exp >> 1        // dịch phải (chia cho 2)
        base = (base × base) mod mod
    return result

Các công thức chính

Thuộc tính	Công thức	Mô tả
Lũy thừa Modular	\(a^b \bmod n\)	Số dư của a^b chia cho n
Định lý nhỏ Fermat	\(a^{p-1} \equiv 1 \pmod{p}\)	Dành cho số nguyên tố p và gcd(a,p)=1
Định lý Euler	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	Dành cho gcd(a,n)=1, trong đó φ là hàm phi Euler
Độ phức tạp phương pháp nhị phân	\(O(\log b)\) phép nhân	Tối đa 2·log₂(b) phép nhân modular
Mã hóa RSA	\(c = m^e \bmod n\)	Mã hóa thông điệp m với khóa công khai (e, n)
Giải mã RSA	\(m = c^d \bmod n\)	Giải mã bản mã c với khóa riêng d

Cách sử dụng Máy tính Lũy thừa Modular

Nhập cơ số (a): Đây là số bạn muốn nâng lên một lũy thừa. Nó có thể là số dương hoặc số âm. Ví dụ, nhập 7 để tính 7^256 mod 13.
Nhập số mũ (b): Đây phải là một số nguyên không âm. Nó đại diện cho lũy thừa. Đối với các ứng dụng mật mã, số này có thể rất lớn (máy tính hỗ trợ lên đến 10^18).
Nhập modulo (n): Đây phải là một số nguyên dương. Đó là số bạn chia để lấy số dư. Trong RSA, đây thường là tích của hai số nguyên tố lớn.
Nhấp Tính toán: Máy tính sẽ tính a^b mod n bằng lũy thừa nhị phân và hiển thị kết quả ngay lập tức.
Xem hoạt ảnh: Nhấn Chạy để xem thuật toán lũy thừa nhị phân thực thi từng bước. Mỗi bit của số mũ được xử lý theo trình tự, cho thấy thuật toán đang bình phương, hay bình phương và nhân.
Xem dấu vết: Bảng từng bước hiển thị mọi phép tính trung gian và so sánh hiệu quả cho thấy lũy thừa nhị phân nhanh hơn bao nhiêu so với phép nhân lặp lại thông thường.

Tại sao Lũy thừa nhị phân lại nhanh

Hãy xem xét việc tính \(2^{1000} \bmod 13\). Cách tiếp cận thông thường đòi hỏi 999 phép nhân. Lũy thừa nhị phân chuyển đổi 1000 sang hệ nhị phân (1111101000), có 10 bit. Nó cần tối đa 9 lần bình phương cộng với một vài lần nhân cho mỗi bit '1' — tổng cộng khoảng 15 phép toán. Điều đó có nghĩa là ít hơn khoảng 98,5% phép toán. Đối với các số mũ quy mô mật mã với hàng trăm chữ số, sự khác biệt là cực kỳ lớn: phương pháp nhị phân mất hàng nghìn phép toán trong khi cách thông thường sẽ yêu cầu nhiều phép toán hơn cả số nguyên tử trong vũ trụ.

FAQ

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

Lũy thừa modular tính (a^b) mod n — nó nâng một cơ số lên một số mũ, sau đó lấy số dư khi chia cho một modulo. Đây là hoạt động cốt lõi trong mật mã khóa công khai (RSA, Diffie-Hellman, ElGamal) và được sử dụng rộng rãi trong lý thuyết số, lập trình thi đấu và khoa học máy tính. Phương pháp lũy thừa nhị phân tính toán điều này một cách hiệu quả trong O(log b) phép nhân.

Thuật toán lũy thừa nhị phân (bình phương và nhân) hoạt động như thế nào?

Lũy thừa nhị phân chuyển đổi số mũ sang biểu diễn nhị phân của nó, sau đó xử lý từng bit từ trái sang phải (hoặc từ phải sang trái). Đối với mỗi bit, nó bình phương kết quả hiện tại theo modulo n. Nếu bit là 1, nó sẽ nhân thêm kết quả với cơ số theo modulo n. Điều này làm giảm số lượng phép nhân từ b−1 (phương pháp thông thường) xuống tối đa 2×log₂(b), giúp việc tính toán với các số mũ khổng lồ trở nên khả thi.

Tại sao lũy thừa modular lại quan trọng trong mật mã học?

Mã hóa RSA tính c = m^e mod n để mã hóa và m = c^d mod n để giải mã, trong đó n là tích của hai số nguyên tố lớn và số mũ có thể dài hàng trăm chữ số. Nếu không có lũy thừa modular nhanh, các hoạt động này sẽ không thể thực hiện được về mặt tính toán. Bảo mật dựa trên thực tế là phép toán ngược (tính logarit rời rạc) được tin là không thể thực hiện được về mặt tính toán.

Cơ số có thể là số âm không?

Có, cơ số âm được hỗ trợ đầy đủ. Máy tính trước tiên sẽ rút gọn cơ số theo modulo n (sử dụng số học modular của Python, luôn trả về kết quả không âm cho n dương). Ví dụ, (−3)^2 mod 7 = 9 mod 7 = 2. Kết quả âm không bao giờ xảy ra vì phép rút gọn modular luôn tạo ra một giá trị trong phạm vi [0, n−1].

Điều gì xảy ra khi modulo bằng 1?

Bất kỳ số nguyên nào modulo 1 đều bằng 0. Điều này là do chia bất kỳ số nguyên nào cho 1 sẽ cho chính số nguyên đó với số dư là 0. Vì vậy, a^b mod 1 = 0 với mọi giá trị của a và b. Máy tính xử lý trường hợp này như một trường hợp đặc biệt.

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy Tính Lũy Thừa Modular" tại https://MiniWebtool.com/vi/may-tinh-luy-thua-modular/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 2026-04-16

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.