该算法产生的数不一定是素数，但该算法产生的数很大几率上可以认为是素数！

素数的两个性质：（只有理解了这两个性质才能理解Miller-Rabin算法！）

性质一：如果p是素数，a是小于p的正整数，则 a^2 mod p =1 当且仅当 a mod p = 1 或 a mod p = -1 mod p =p-1 

性质二：设p是大于2的素数，我们有 p-1=2^k * q，k>0，q为奇数，设a是整数且1<a<p-1，则以下两个条件之一成立：

    1. a^q 模 p 和 1 同余，即 a^q mod p =1；

    2. 在整数 a^q，a^(2q)，... a^(2^(k-1)*q)里存在一个数，模p和-1同余；

证明：若n 是素数，则由费马定理（a^(n-1)  mod n = -1 = n-1)，由于 p-1 =2^k*q ，则 a^(p-1) mod p = a ^ (2^k*q) mod p = 1 ，因此以下数列：

a^q，a^(2q)，a^(4q) ... a^(2^(k-1)*q)

最后一个数为1（费马定理），每一个数都是前一个数的平方，因此下面两条必有一条是正确的：

    1. 数列的第一个数，以及其后的所有数都为1；

    2.数列里有些数不为1，但他们的平方模p后为1，根据素数的第一性质，我们知道满足这个条件的唯一整数为 p-1，因此数列中必有一个为p-1；

证毕；

算法：

1.找到整数 k，q，其中 k>0，q为奇数，满足 n-1=2^k *q；

2.随机选择一个数 a，1<a<n-1；

3. if  a^q mod n=1  then  return该数可能为素数

4.for j=0 to k-1 do

    if   a^(2^j*q) mod n = n-1  then return该数可能为素数

5.return 该数为合数

Miller-Rabin算法