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

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

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:

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

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

1. 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.
2. 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).
3. 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.
4. 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.
5. 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.
6. 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

Các công cụ liên quan khác:

Phép toán toán học nâng cao:

• Máy Tính Antilog
• Máy tính hàm Beta
• Máy tính hệ số nhị thức
• Máy tính phân phối xác suất nhị thức
• Máy tính Bitwise
• Máy tính Định lý Giới hạn Trung tâm
• Máy tính kết hợp
• Máy tính hàm lỗi bổ sung
• Máy tính số phức
• Máy tính Entropy
• Máy tính chức năng lỗi
• Máy tính giảm dần theo cấp số nhân
• Máy tính tăng trưởng theo cấp số nhân
• Máy tính Tích phân Lũy thừa
• máy-tính-số-mũ-độ-chính-xác-cao Nổi bật
• Máy tính giai thừa
• Máy tính Hàm Gamma
• Máy tính tỷ lệ vàng
• Máy tính Nửa đời
• Máy tính phần trăm tăng trưởng
• Máy tính hoán vị
• Máy tính Phân phối Poisson Nổi bật
• Máy tính căn bậc của đa thức với các bước chi tiết
• Máy tính xác suất
• Máy tính phân bố xác suất
• Máy tính Tỷ lệ
• Máy tính công thức bậc hai
• Máy Tính Khoa Học
• Máy tính ký hiệu khoa học
• Máy Tính Chữ Số Có Nghĩa Mới
• Máy tính tổng khối
• Máy tính tổng các số liên tiếp
• Máy tính Tổng Bình phương
• Công cụ tạo bảng chân trị
• Máy tính lý thuyết tập hợp
• Công cụ tạo Biểu đồ Venn (3 Tập hợp)
• Máy tính Định lý Số dư Trung Quốc
• Máy tính Hàm Phi Euler
• Máy tính Thuật toán Euclid Mở rộng
• Máy tính Nghịch đảo Nhân theo Mô-đun
• Máy tính Phân số liên tục
• Máy tính Đường đi Ngắn nhất Dijkstra
• Máy tính Cây khung nhỏ nhất
• Trình xác thực dãy bậc đồ thị
• Máy tính Hoán vị lệch (Giai thừa phụ)
• Máy tính số Stirling
• Máy tính Nguyên lý Chuồng bồ câu
• Máy tính Phân phối Dừng Chuỗi Markov
• Máy Tính Làm Tròn Mới
• Máy Tính Phân Phối Nhị Thức Âm Mới
• Máy tính Hoán vị Có lặp Mới
• Máy Tính Lũy Thừa Modular Mới
• Máy Tính Căn Nguyên Thủy
• Công Cụ Rút Gọn Đại Số Boolean Mới
• Công cụ Giải Bản đồ Karnaugh (K-Map) Mới
• Máy Tính Tô Màu Đồ Thị Mới
• Máy Tính Sắp Xếp Topo Mới
• Máy Tính Ma Trận Kề Mới
• Máy tính Bao hàm - Loại trừ Mới
• Công cụ Giải Quy hoạch Tuyến tính Mới
• Trình Giải Bài Toán Người Du Hành (TSP) Mới
• Công cụ Kiểm tra Đường đi Hamilton Mới
• Trình Kiểm Tra Đồ Thị Phẳng Mới
• Máy Tính Luồng Mạng (Luồng Cực Đại) Mới
• Trình giải Bài toán Hôn nhân Ổn định Mới
• Máy Tính Bậc Lý Thuyết Nhóm Mới
• Máy tính Vành và Trường Mới