C++ 程序实现费马小定理
c++server side programmingprogramming
费马小定理是初等数论的基本结果之一，是费马素数测试的基础。该定理以皮埃尔·德·费马 (Pierre de Fermat) 的名字命名，他于 1640 年提出了该定理。该定理指出，如果 p 是素数，则对于任何整数 a，数字 a p-a 都是 p 的整数倍。
算法
开始 函数 power() 用于计算模 M 下的 a 的 b 次幂 函数 modInverse() 用于查找模 m 下的 a 的模逆元: 设 m 为素数 如果 a 和 m 互质，则 模逆为 a^(m - 2) mod m 结束
示例代码
#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<<"输入数字以查找模乘逆元:";
cin>>a;
cout<<"输入模数值:";
cin>>m;
cout<<modInverse(a, m)<<endl;
}
输出
输入数字以查找模乘逆元:26 输入模数值:7 3
