c - RSA key 生成

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;

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