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

回答

相關問題