本文主要是介绍【密码学】费马小定理素性检测(C++代码实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
![](/upload/202110/04/202110041411306229.png)
#include <NTL/ZZ.h>
#include<iostream>
using namespace std;
using namespace NTL;
long PrimeTest(const ZZ& n, long t)
{
if (n <= 1) return 0;
//用2000以内的素数对n进行初筛
PrimeSeq s; // 生成一个素数数列
long p;
p = s.next(); // first prime is always 2
while (p && p < 2000) {
if ((n % p) == 0) return (n == p);
p = s.next();
}
//Fermat法推演n的素性
ZZ x;
for (long i = 0; i < t; i++) {
x = RandomBnd(n); // 随机数 between 0 and n-1
if ((x,n)==1 && PowerMod(x,n-1,n)!=1)
return 0;
}
return 1;
}
int main()
{
ZZ n;
long t;
cout << "请输入Fermat待检测的n: ";
cin >> n;
cout << "请输入Fermat检测次数t:";
cin >> t;
if (PrimeTest(n, t))
cout << "n是素数\n";
else
cout << "n是合数\n";
}
这篇关于【密码学】费马小定理素性检测(C++代码实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!