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

相关文章