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

Question

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

3

我正在阅读 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;
}

如果它的名称可以说明它的功能，那么它检查一个数字是否为质数。然而，我无法弄清它是如何做到的。

我可以理解每个语句的作用，但我不知道它是如何工作的。

- yasar

2

在调试器中运行，并调用一个小质数，然后逐行步进代码，同时查看所有变量的变化以及它们变为什么。 - Some programmer dude

1

@yasar，它是基于小费马定理的。 - advocateofnone

2

http://en.wikipedia.org/wiki/Fermat_primality_test - wimh

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- advocateofnone · Accepted Answer

基本上如果一个数字q是质数，费马定理表明：

a^{(q - 1)} = 1 (mod q)

其中a和q是互质的。

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