这个 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 是质数，这个方法会正确地将它检测为质数，但如果它是复合的，它可能会检测到它是质数，这种可能性很低。虽然这种方法不如其他方法有效。

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

How does this isPrime function work?

c

primes