โปรแกรม C++ ใช้ทฤษฎีบทเล็กของเฟอร์มาต์ (Fermat's Little Theorem)

ทฤษฎีบทเล็กของเฟอร์มาต์ (Fermat's Little Theorem) เป็นหนึ่งในผลลัพธ์พื้นฐานของจำนวน론 初等 และเป็นพื้นฐานของ Fermat primality test ทฤษฎีบทนี้ได้ชื่อจาก Pierre de Fermat ซึ่งระบุในปี 1640 ทฤษฎีบทระบุว่า ถ้า p เป็นจำนวนเฉพาะ สำหรับจำนวนเต็ม a ใดๆ จำนวน a^p - a จะเป็นจำนวนเท่าของ p

อัลกอริทึม

Begin
    ฟังก์ชัน power() ใช้คำนวณ a ยกกำลัง b ภายใต้ modulo M
    ฟังก์ชัน modInverse() หา modular inverse ของ a ภายใต้ modulo m:
        ให้ m เป็นจำนวนเฉพาะ
        ถ้า a และ m เป็น relatively prime แล้ว
            modulo inverse คือ a^(m - 2) mod m
End

ตัวอย่างโค้ด

#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<<"Enter number to find modular multiplicative inverse: ";
    cin>>a;
    cout<<"Enter Modular Value: ";
    cin>>m;
    cout<<modInverse(a, m)<<endl;
}

ผลลัพธ์

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
3