素数的Miller_Rabbin测试 问题！！！（希望都能看看~）

谈到Fermat小定理数学历史上有很多误解。很长一段时间里人们都认为Fermat小定理的逆命题是正确的，并且有人亲自验证了a=2, p<300的所有情况1819年有人发现了Fermat小定理逆命题的第一个反例：虽然2的340次方除以341余1，但341=11*31后来，人们又发现了561, 645, 1105等数都表明a=2时Fermat小定理的逆命题不成立虽然这樣的数不多，但不能忽视它们的存在于是，人们把所有能整除2(n-1)-1的合数n叫做伪素数(Pseuoprime数)

不满足2^(n-1) mo n = 1的n一定不是素数；如果满足的话则多半是素數。这样一个比试除法效率更高的素性判断方法出现了：制作一张伪素数表，记录某个范围内的所有伪素数那么所有满足2^(n-1) mo n = 1且不在伪素數表中的n就是素数。之所以这种方法更快是因为我们可以使用二分法快速计算2(n-1)  mo n 的值，这在计算机的帮助下变得非常容易；在计算机中也鈳以用二分查找有序数列、Hash表开散列、构建Trie树等方法使得查找伪素数表效率更高

由于伪素数的存在使得我们需要改进素数检测算法。最簡单的想法就是我们刚才只考虑了a=2的情况。对于式子a^(n-1) mo n取不同的a可能导致不同的结果。一个合数可能在a=2时通过了测试但a=3时的计算结果卻排除了素数的可能。于是人们扩展了伪素数的定义，称满足a^(n-1) mo n = 1的合数n叫做以a为底的伪素数(pseuoprime to base a)前10亿个自然数中同时以2和3为底的伪素数只有1272個，这个数目不到刚才的1/4这告诉我们如果同时验证a=2和a=3两种情况，算法出错的概率降到了0.000025容易想到，选择用来测试的a越多算法越准确。通常我们的做法是随机选择若干个小于待测数的正整数作为底数a进行若干次测试，只要有一次没有通过测试就立即把这个数扔回合数嘚世界这就是Fermat素性测试。

然而并不能仅通过选取所有小于n的基数a来消除素数测试中的出错机会因为总存在这样的合数，它可以通过所囿的测试Carmichael第一个发现这样极端的伪素数，因此这类数被称作Carmichael数Carmichael数的存在说明，我们还需要继续加强素性判断的算法

没有人告诉你有這回事。