RSA密钥生成

//test whether it is prime number ot not 
int prime_test(long int prime_number) 

{ 
     long int a, p; 
     srand((unsigned)time(NULL)); 

     //0 and 1 not meaning for prime test. 
     a = rand() % (prime_number - 2) + 2; 
     printf("a -> %li\n", a); 

     //Lehmann Algorithm, p = a^((prime_number-1)/2) mod prime_number 
     p = (long int)pow(a, (prime_number - 1)/2) % prime_number; 
     printf("p -> %li\n", p); 

     if(p != 1 & (prime_number - p) != 1) 
     { 
        printf("Enter number is not prime number.\n"); 
        return 0; 
     } 
     else 
     {  
        printf("Enter number is prime number.\n"); 
        return 1; 
     } 
}

我的问题是，为什么我得到阴性p -984，1997年实际上是一个素数，
应该是1或-1无论是。输出就像下面：RSA密钥生成

输入素数p：1997年
一个 - > 1557
p - > -984
输入的号码是不是质数！
temp1目录 - > 0
请重新输入素数p：

来源

2015-05-22 Seven

这是用于大素数测试的函数，它适用于像13和17这样的非常小的数字，但是一旦我输入大数字，就会出现负数，所以我在这里发帖，可以有人给我答案吗？ – Seven

'long int'远远不够你想要的。出于测试目的将其改为'long long int'。但即使这样还不足以用于任何实际使用，您需要使用bigint。 – mtijanic

@mtijanic：OP的例子对于bigint来说有点太大了，大约有38个宇宙。 – usr2564301

1557^998不太适合到long int。

更建设性的一点：如果你计算p像这样，它会需要更长的时间，但要避免溢出：

p = 1; 
for (i=0; i<(prime_number-1)/2; i++) 
    p = (p*a) % prime_number;

有（非常好）的方式来优化，但我会将其作为练习。

来源

2015-05-22 14:40:21

你的想法是非常有用的，我创建了一个函数来模拟基础和权力，即a^p mod m，在这个函数中，我们可以这样做： – Seven

for（i = 1; i Seven

temp = 1;在for循环中，我们做temp =（temp * base）％mod;这样我就可以让我的程序起作用。大声笑 – Seven

回答

相关问题