【密码学】费马小定理素性检测（C++代码实现）

本文主要是介绍【密码学】费马小定理素性检测（C++代码实现），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#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++代码实现）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！