RSA 密钥生成

Question

//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。输出如下：

输入素数p:1997
一个 -> 1557
p -> -984
输入的数字不是质数！
温度 1 -> 0
请重新输入素数p:

Answer 1

1557 ^ 998 不太适合 long int。

更具建设性：如果您像这样计算 p，则需要更长的时间，但要避免溢出：

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

有（非常好的）方法可以优化它，但我会把它留作练习。

RSA 密钥生成

RSA key generation

c

rsa

number-theory