C ++程序实现费马小定理
费马小定理是基本数论的基本结果之一，是费马素数检验的基础。该定理以皮埃尔·德·费马特（PierredeFermat）的名字命名，皮埃尔·德·费马特（PierredeFermat）于1640年指出。定理指出，如果p是质数，那么对于任何整数a，数ap–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