分类：
2010-08-03 00:20:47
这篇日志想简单介绍一下素数的判定。
有一个以前开始经常使用的方法，很原始，计算的效率很低，使用的范围很狭窄，主要在检验比较小的数。大致算法是：从1到n的平方根，都试除，看是否能够除尽。
另外一个算法，Miller-Rabin素数测试方法：
约在2500年前我国古代先贤就发现一个规律，2^2 -2 是2的倍数，2^3-2是3的倍数；2^5 – 2 是5的倍数；2^7 –
2是7的倍数；2^11-2是11的倍数；而且2、3、5、7、11都是素数。于是便提出了一个猜想，2^(n-1) ≡1 mod n ,则n是素数。
不过很遗憾，这个猜想是不成立的。法国数学家赛努斯首先提出2^340 ≡ 1 mod341,但是341不是素数。
Miller-Rabin方法正是基于上述的思路。
我们要判定n是不是素数？我们可以随机的取比较小的素数来做底，验证k^(n-1)≡1 mod n 是否成立？？
选取比较小的素数，是为计算的方便；一般我们选择5个素数来测试这个，其精度基本上可以达到要求。
http://www.cnblogs.com/Knuth/archive/2009/09/04/1559949.html
