2.20.波克林顿检验pocklington primality test原创

这节课讲伯克林顿解。伯克林顿检验是一种确定性的算法，用于确定一个数字是否是数数。我。这方面跟之前讲的卢卡斯检验。是一样的。里面会用到质因数的分解，所以没有多项式实验算法。空间复杂多。也是那个。是根的原因是里面会用到质因数的分解。N原理，首先A的N减一次方和1是否同于，这个就是非马小定理。跟之跟之前讲的卢卡斯属性测试里面是一样的。嗯，满足了微马小定律过后。这个地方。跟之前讲嘛，卢甘斯塑形测试。

对N-1，然后拆分成。进行质因数的分解，然后拆分成很多的扣。这个波克林顿检验也是一样的，都需要拆分折扣。但是条件，嗯，最最重要。公式不不一样吗？这个地方变成了GCD。然后A到Q到N-1。然后减1。和N，然后再取一个最大公约数。然后判断这个是否等于等于。注意这个Q是每个数因数，也就是说GCD这个式子。对每一个数因数的课都必须相等。如果这两个条，这2个结论都满足，那么N就是数数。

如果，如果不存在这样的A，那么N肯定就是合数。A是，虽然是1 1到N1到N的范围，但是实际上不需要1到N之间的便利。实际上。跟之前讲的卢卡斯算法是一样的。A从2~6乘以勒勒根之间便利。我们看大铁过程跟卢卡斯的塑形测试是一样的，区别在于波克林顿检验，试求GCD，也就是最大公约数。可以只针对部分因素扣，但我这个地方。并并不是求部分的输赢数扣1。还是求所谓的数因数克？我们看一下代码。

这是波克林顿检验，这个跟之前讲的卢卡斯的算法是一样的。这个地方就是飞马检验。嗯，下一步。这一步就是。急求GCD。要要满足所所有的GGCD，然后。这才算通过。如果通过不了的话，最终就返回false，我们看一下运行结果。我们可以看到触犯次数是0，也就是说并没有误。并没有尾数数。这是一个确定性的算法。嗯，我们只需要记住两个公式，第一个是飞马小定理，第二个是求GCD。

嗯，然后呢，还要注意一点。求GCD的是对N-1。所有的输赢。出口。从A。是存在，存在一个整数A。