大素数的费马素性检验

Question

我目前正在尝试为学校项目实施 RSA 加密算法。在研究之后，我认为生成我自己的素数也会很有趣。我正在使用 gmp 库来存储数字。

一些消息来源说，这通常是通过使用筛选方法然后对数字进行概率测试来完成的，在我的例子中，我从费马测试开始：

a^(potPrime-1) ≡ 1 (mod potPrime)

我遇到的问题是计算“a^(potPrime-1)”，我在 gmp 库中找不到可以计算另一个 mpz_t 次幂的函数 mpz_t所以我写了我自己的，这实际上是一个持续循环的一段时间，直到我将数字本身乘以所需的次数。这适用于小数字，但当 potPrime 可以达到 2^2048 时，这个解决方案是不够的。

有谁知道我该如何解决这个问题？这是费马检验的代码：

int fermatTest(mpz_t potPrime, mpz_t a) //The fermat test is a mathimatical test that will determine if a number is potentialy prime.
{                                       //a is a random number between ]1;p-1[
    int result;
    mpz_t potPrimeMin1,aSqPotPrimeMin1,val1; //decalre mpz type value, val1=1
    mpz_init(potPrimeMin1); //initialises the mpz type value of the number containing potPrime minus 1
    mpz_init(aSqPotPrimeMin1);//value of a^(p-1)
    mpz_init(val1); //a mpz type var where val1 is allways 1
    mpz_set_ui(val1,1);

    mpz_sub_ui(potPrimeMin1,potPrime,1); //subtracts 1 from potPrime and stores it in potPrimeMin1

    mympz_pow(aSqPotPrimeMin1,a,potPrimeMin1);//aSqPotPrimeMin1=a^potPrimeMin1

    result = mpz_congruent_p(aSqPotPrimeMin1,val1,potPrime); //test checks if a^(potPrime-1) ≡ 1 (mod potPrime) - returns non zero if congruent

    //returns non zero if operation is true, 0 if not

    mpz_clear(potPrimeMin1);//frees the variables used
    mpz_clear(aSqPotPrimeMin1);
    mpz_clear(val1);

    return result;
}

这是 pow 函数的代码：

int mympz_pow(mpz_t result, mpz_t base, mpz_t power)
{
    mpz_t i;
    mpz_init(i);
    mpz_set_ui(i,1);
    mpz_set(result,base);
    //mpzPrint("1",result);
    while(mpz_cmp(i,power) < 0)
    {
        mpz_mul(result,result,base);
        //mpzPrint("2",result);
        mpz_add_ui(i,i,1);
        mpzPrint("pow",power);
        mpzPrint("i",i);
    }
    //mpzPrint("3",result);
    mpz_clear(i);
    return 1;
}

Answer 1

Gmp 有一个函数 mpz_powm 可以进行模幂运算。如果你想自己做，使用square-and-multiply算法：

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x

这需要的时间是指数的对数而不是线性的，就像您的算法那样。或者您可能更喜欢使用 mpz_probab_prime_p 并让 gmp 为您完成所有工作。

大素数的费马素性检验

Fermat primality test for big primes

c

linux

primes

gmp