游客您好，欢迎来到黑客世界论坛！您可以在这里进行注册。

赤队小组-代号1949（原CHT攻防小组）在这个瞬息万变的网络时代，我们保持初心，创造最好的社区来共同交流网络技术。您可以在论坛获取黑客攻防技巧与知识，您也可以加入我们的Telegram交流群 共同实时探讨交流。论坛禁止各种广告，请注册用户查看我们的使用与隐私策略，谢谢您的配合。小组成员可以获取论坛隐藏内容！

TheHackerWorld官方

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

发布于2022年10月15日3年前

?i=20211004131742613.png?,type_ZHJvaWRzY

#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";
}