c - 这个 isPrime 函数是如何工作的？

Question

我正在阅读 http://www2.informatik.hu-berlin.de/~weber/slipOff/hashmap_c.html并且很难理解这个函数是如何工作的:

static unsigned long isPrime(unsigned long val)
{
  int i, p, exp, a;

  for (i = 9; i--;)
  {
    a = (rand() % (val-4)) + 2;
    p = 1;
    exp = val-1;
    while (exp)
    {
      if (exp & 1)
        p = (p*a)%val;

      a = (a*a)%val;
      exp >>= 1;
    }

    if (p != 1)
      return 0;
  }

  return 1;
}

如果它的名字能说明它的作用，它会检查一个数是否为质数。但是，我不知道它是如何做到的。

我能理解每条语句的作用，但我不明白它是如何工作的。

Answer 1

基本上，如果一个数 q 是质数，则费马定理指出

a(q - 1) = 1 (mod q)

其中 a 和 q 互质。

所以基本上，while 循环只是计算一些随机数的 val-1 次方，并取模 val。如果最终结果为 1，则表示 val 是素数，否则不是。但一般来说，即使 p 不是素数，对于 a 的一些随机值也是如此。因此我们通常取几个随机数并重复相同的过程，如果最后都给出 p=1 我们说 val 是素数的概率很高(外循环是为了重复这个过程，迭代次数越多，你的答案正确的概率就越大)。所以基本上，如果 val 是质数，此方法将正确地将其检测为质数，但如果它是复合的，它可能会检测为质数，但概率很低。虽然这种方法不如其他方法有效。