2.14.米勒拉宾素性检验Miller-Rabin primality test原创

这节课讲米拉拉宾塑性检验，米勒拉宾检验跟之前讲的非法检验都是概率性的算法。用于确定一个数字是不是可能的数数。原理，这个米勒拉宾检验有两个依据。第一个一句跟之前讲的飞马检验是一样的。都是根据飞马小丁米判断。这棵树是否是？是数数，如果不满足这个同因式N肯定是好数，第二步都不用判断了。如果满足这个费马小定理，那就需要根据第二步去判断它。第第二个依据，也就嗯，就是A的平方和1同。X等于正负一的时候。嗯，N是可能的数数。如果，如果X不等于±1。

嗯，肯定是合数。X不等于正负的时候，X叫做非平方的平方根。如果X等于±1。X叫做平方的平方根。嗯，N是一个数数，N-1就是一个偶数。N-1=U×2的T次方又是一个很大的。激素。嗯，P是一个大于等于的小正数。嗯，复杂度方面，这点跟之前讲的飞马减是一样的，时间复杂度是K×log n的三次方，空间度是1。嗯，举例这里举了好，举了几个例子。嗯，注意看举例1里面有四项。

举例2里面有三项，这个四项是什么意思？也就就是。T+1=4 T就等于3了。02。有三项，T+1=3，因此T=2。嗯，如何判断呢，这个这5点我我就不不念了，直接看这个，这个叫二次探测。先看左右项是不是是1。我看这几个例子，除了举例6最后一项是负一以外，其他的都是1。所以举例6这个N肯定是合数。And.再看是否权益，这是第二个判断依据了。也就是这个。则X平方和1同于。就是看X是不是平方的平方。

根还是非平方的平方根。是不是权益？嗯，举例4是选一所，所以举例4里面N是可能的数数。嗯，然后再看是否经历-1的过程。第一项。举例1里面第一项就是-1了，他肯定是尽量-1的过程，所以但是举例1可能是输入举例2里面。中间有负一。因此经历了负一的过程，所以举举例2，它也是一个数数。In an.3511，这个5突然变成1了，并中间并没有经历会议的过程。所以举例3它是一个合数。嗯，再再看举例，557突然变成1了。

嗯，这肯定也是合数。我们看一下代码是怎么写的。嗯。小于等于1的，嗯。肯定不是叔叔。那等于22肯定是数数，这这这是做了一个特别的判断，后面就是把N-1。彩纹成有成腰的体脂吗？嗯，下一步X。等于A的U次方，也就是举例里面的第一项。然后便利。便利7次。X=X平方。

也就是第二项。然后判断。X是不是等于1？这个第二项确实是等于1的。然后再看X。不等于1，并且不等于单减1，也就是负一。那那么就直接返回合数了。这，这是什么意思？我们看距离物里面。第二项它是等于1的，也就是这个条件。然后第一项不等于±1。这个D项刚好就不等于正负一了，所以它是一个合数。这里面代码确实确实也是等于负一的。

然后依次循环。这个循环就。第一次是第二项，第一次循环是第二项和第一项做判断。第二个循环就是。第3个。呃，第二第三项和第二项做判断，一直到最后。最后的X就一定是等于最后一项的。最后一项判断是否是否等于1。最后项一定等于1的如果我如果，如果不等于1。嗯，那肯定是返回force。等于1的时候，那那。那就是可能的数数。这个可能的尾尾数数，也就是说本这些数本来都是合数，结果被误判成数数了。

我们看一下代码。为敌的。嗯，我们可以看到204732774033。20473274033。刚刚好有一只。

我们再看以3为例的。121286703。跟这边是一致的。嗯，我的猜想，这这是什么意思？我的猜想就是。嗯。2为底，一直到勒个勒根的平方为底。这个范围并没有找到返利。我们可以看一下代码是怎么写的。这个4949那个。

那个的。然后这个再求一次那个。然后这个就是。Log log个N×log log个N，也就是这个。然后便利。从2到。那个那个的。那个log n的平方。然后呢，都用米勒拉宾算法去检验它。然后我们看一下运行的结果。我们可以看到错判次数是0意思，没意思，是没有误判的。我的个人猜测。这个第二点是否是确定性算法呢？

目前我是没有找到返利的。这，这是参考的资料。