Chương trình C++ triển khai Định lý nhỏ Fermat

Định lý nhỏ Fermat là một trong những kết quả cơ bản của lý thuyết số sơ cấp và là cơ sở cho kiểm tra nguyên tố Fermat. Định lý được đặt tên theo Pierre de Fermat, người đã nêu ra nó vào năm 1640. Định lý phát biểu rằng nếu p là một số nguyên tố, thì với bất kỳ số nguyên a nào, số a^p - a là bội số nguyên của p.

Thuật toán

Bắt đầu
    Hàm power() dùng để tính a mũ b dưới modulo M
    Hàm modInverse() để tìm nghịch đảo modulo của a dưới modulo m:
        Giả sử m là số nguyên tố
        Nếu a và m nguyên tố cùng nhau, thì
            Nghịch đảo modulo là a^(m - 2) mod m
Kết thúc

Mã ví dụ

#include <iostream> 
using namespace std; 

int pow(int a, int b, int M) { 
    int x = 1, y = a; 
    while (b > 0) { 
        if (b % 2 == 1) { 
            x = (x * y); 
            if (x > M) 
                x %= M; 
        } 
        y = (y * y); 
        if (y > M) 
            y %= M; 
        b /= 2; 
    } 
    return x; 
} 

int modInverse(int a, int m) { 
    return pow(a, m - 2, m); 
} 

int main() { 
    int a, m; 
    cout << "Nhập số để tìm nghịch đảo modulo: "; 
    cin >> a; 
    cout << "Nhập giá trị modulo: "; 
    cin >> m; 
    cout << modInverse(a, m) << endl; 
}

Kết quả

Nhập số để tìm nghịch đảo modulo: 26 
Nhập giá trị modulo: 7 
3