费马小定理c++题目

### 关于费马小定理的 C++ 编程练习 #### 使用费马小定理验证素数 费马小定理指出如果 \( p \) 是一个质数，那么对于任何整数 \( a \)，\( a^p-a \) 将能被 \( p \) 整除。换句话说，当 \( p \) 不是 \( a \) 的因子时，则有 \( a^{(p-1)}\equiv 1 (\text{mod}\,p) \)[^1]。 下面是一个简单的程序来测试给定的数字是否可能是素数： ```cpp #include <iostream> using namespace std; bool modularExponentiation(int base, int exp, int modulus){ long result = 1; while (exp > 0){ if (exp % 2 == 1){ // If exponent is odd. result = (result * base) % modulus; } base = (base * base) % modulus; // Square the base and halve the exponent. exp /= 2; } return result == 1; } // Function to check primality using Fermat's Little Theorem bool fermatPrimalityTest(int n, int iterations=5){ if(n<=1 || n==4)return false; if(n<=3)return true; for(int i=0;i<iterations;++i){ int a=rand()%(n-3)+2; if(!modularExponentiation(a,n-1,n)){ return false; } } return true; } int main(){ cout << "Enter number to test: "; int num; cin >> num; if(fermatPrimalityTest(num)) cout<<num<<" might be prime."<<endl; else cout<<num<<" is not prime."<<endl; return 0; } ``` 这段代码实现了基于费马小定理的概率性素数检测算法[^2]。 #### 计算模逆元 另一个常见的应用是在计算两个大数之间的乘法逆元时使用该理论。这里提供了一个函数用于找到 `a` 对于模块 `m` 的乘法逆元（假设它们互质），即求解满足条件 \( ax ≡ 1(\text{mod} m)\) 中未知量 \( x \): ```cpp long multiplicativeInverse(long a,long phiN){ return modularExponentiation(a,phiN-1,phiN); } ``` 此方法利用了欧拉定理的一个特例——费马小定理，在已知 \( φ(m)=m−1 \) 并且 \( gcd(a,m)=1 \) 下简化了运算过程[^3]。