Jump to content
  • Hello visitors, welcome to the Hacker World Forum!

    Red Team 1949  (formerly CHT Attack and Defense Team) In this rapidly changing Internet era, we maintain our original intention and create the best community to jointly exchange network technologies. You can obtain hacker attack and defense skills and knowledge in the forum, or you can join our Telegram communication group to discuss and communicate in real time. All kinds of advertisements are prohibited in the forum. Please register as a registered user to check our usage and privacy policy. Thank you for your cooperation.

    TheHackerWorld Official

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

 Share


Recommended Posts

?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";
}
Link to post
Link to comment
Share on other sites

 Share

discussion group

discussion group

    You don't have permission to chat.
    • Recently Browsing   0 members

      • No registered users viewing this page.
    ×
    ×
    • Create New...