โปรแกรม C++ เพื่อใช้ทฤษฎีบทน้อยของแฟร์มาต์

ทฤษฎีบทเล็กๆ ของแฟร์มาต์เป็นหนึ่งในผลลัพธ์พื้นฐานของทฤษฎีจำนวนมูลฐาน และเป็นพื้นฐานสำหรับการทดสอบเบื้องต้นของแฟร์มาต์ ทฤษฎีบทนี้ตั้งชื่อตามปิแอร์ เดอ แฟร์มาต์ ซึ่งระบุไว้ในปี ค.ศ. 1640 ทฤษฎีบทนี้ระบุว่าหาก p เป็นจำนวนเฉพาะ ดังนั้นสำหรับจำนวนเต็ม a ใดๆ ตัวเลข a p–a จะเป็นผลคูณของจำนวนเต็มของ p

อัลกอริทึม

Begin
   Function power() is used to compute a raised to power b under modulo M
   function modInverse() to find modular inverse of a under modulo m :
   Let m is prime
   If a and m are relatively prime, then
      modulo inverse is 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