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

Định lý nhỏ Fermat là một trong những kết quả cơ bản của lý thuyết số cơ bản và là cơ sở cho phép thử tính nguyên thủy Fermat. Định lý được đặt theo tên của Pierre de Fermat, người đã phát biểu 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

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

Mã mẫu

#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;
}

Đầu ra

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