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