费马小定理c++

### 费马小定理的C++实现 费马小定理指出，如果 \( p \) 是一个素数，且整数 \( a \) 不被 \( p \) 整除，则有如下关系成立：\[ a^{p-1} \equiv 1 \ (\text{mod}\ p) \]。利用这一性质，可以通过快速幂算法高效地验证该结论。 以下是一个完整的C++程序实现： ```cpp #include <iostream> using namespace std; // 快速幂取模函数 long long fast_pow(long long base, long long exp, long long mod) { long long result = 1; while (exp > 0) { if (exp & 1) { // 如果指数最低位为1 result = (__int128(result) * base) % mod; // 防止溢出 } base = (__int128(base) * base) % mod; // 平方基数并取模 exp >>= 1; // 右移一位相当于除以2 } return result; } // 判断是否满足费马小定理 bool fermat_little_theorem(long long a, long long p) { if (p <= 1 || a % p == 0) return false; // 排除非素数或a能被p整除的情况 return fast_pow(a, p - 1, p) == 1; // 计算a^(p-1) % p 是否等于1 } int main() { long long a, p; cout << "请输入a和p：" << endl; cin >> a >> p; if (fermat_little_theorem(a, p)) { cout << "满足费马小定理" << endl; } else { cout << "不满足费马小定理" << endl; } return 0; } ``` 上述代码中定义了一个`fast_pow`函数用于执行快速幂运算[^1]，并通过它来检验给定的\(a\)和\(p\)是否符合费马小定理的要求[^2]。注意，在实际应用中需考虑边界条件以及可能存在的伪素数问题[^3]。 ---

### 关于费马小定理的 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]。