查看文章 |
对于2-伪素数表的每一个伪素数，寻找最小的可以判定它们是合数的底数，我把这个底数称之为最小可判定底数。特别地，对于绝对伪素数，它的最小质因子即是它的最小可判定底数。由于已经证明了绝对伪素数至少有三个质因子，所以这个最小质因子一定不大于n^(1/3)。下面就是我找到的最小可判定底数列表： 341 3 561 3 645 3 1105 5 1387 3 1729 7 1905 3 2047 3 2465 5 2701 5 ... ... ... 4286813749 3 4288664869 3 4289470021 5 4289641621 3 4289884201 3 4289906089 3 4293088801 3 4293329041 3 4294868509 7 4294901761 3
通过统计这个列表，我发现了一个规律，那就是所有的最小可判定底数都不大于n^(1/3)，由前述可知，对于绝对伪素数，这个结论显然成立。而对于非绝对伪素数，虽然直观上觉得它应该比绝对伪素数好判定出来，但是我无法证明出它的最小可判定底数都不大于n^(1/3)。不过没关系，这个问题就作为一个猜想留给数学家来解决吧，更重要的是我已经通过实验证明了在32位机器数范围内这个结论成立。 我们还有没有更好的方法来进一步减小最小可判定底数的范围呢？有的！我们可以在计算平方数时进行二次检测，下面是进行了二次检测后重新计算的最小可判定底数列表： 341 2 561 2 645 2 1105 2 1387 2 1729 2 1905 2 2047 3 2465 2 2701 2 ... ... ... 4286813749 2 4288664869 2 4289470021 2 4289641621 2 4289884201 2 4289906089 2 4293088801 2 4293329041 2 4294868509 2 4294901761 3
很显然，二次检测是有效果的，经过统计，我发现了新的规律，那就是经过二次检测后所有的最小可判定底数都不大于n^(1/6)，真的是开了一个平方呀，哈哈！这个结论的数学证明仍然作为一个猜想留给数学家们吧。我把这两个猜想叫做费尔马小定理可判定上界猜想。而我已经完成了对32位机器数范围内的证明。 通过上面总结的规律，我们已经可以设计出一个对32位机器数进行素数判定的 O(n^(1/6)*log(n)) 的确定性方法。但是这还不够，我们还可以优化，因为此时的最小可判定底数列表去重后只剩下了5个数（都是素数）：{2,3,5,7,11}。天哪，就是前5个素数，这也太容易记忆了吧。 不过在实现算法时，需要注意这些结论都是在2-伪素数表基础上得来的，也就是说不管如何对2的判定步骤必不可少，即使当2>n^(1/6)时。 还有一些优化可以使用，经过实验，当n>=7^6时，可以不进行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正确的。这样就可以把判定次数降为4次以下，而每次判定只需要进行4log(n)次乘除法（把取余运算也看作除法），所以总的计算次数不会超过16log(n)。经过实验，最大的计算次数在n=4294967291时出现，为496次。 |
