素数测试的基础是费马小定理：
对于素数p，任意0<a<p，有；变化形式为
。
费马小定理逆定理不成立，所以费马测试不保证正确。强化版测试方法就是Miller-Rabin素数测试：
在测试通过，且p-1还有因数2的情况下，进一步测试
，如此重复除2的测试直到指数不再被2整除或者mod余数不再是1。最后那次测试如果mod结果不是1和p-1则可否定p是素数。
从费马测试到Miller-Rabin测试的理论依据，网上很多博文都瞎抄了个二次探测定理，然而根本不适用，实际的推论过程如下。
初次测试指数，其后每次测试都除2，依次记为
。
对于，如果可以继续除2测试，即
，那么可以做如下变换
将mod改用整除形式表示
因为前提p是素数，无法再拆分因数，所以若左边两个括号不是直接等于p和c，就只能将c拆分因数
即左边两个括号必有一个是p的整数倍，若是前者，则；若是后者，则
。
特殊情况左边有一个括号是0，那么，同样符合上述结论。
附一定范围内Miller-Rabin素数测试的a值选择，摘自wiki：
（16bit符号数范围内确保素数判断正确）
（32bit符号数范围内确保素数判断正确）
（64bit符号数范围内确保素数判断正确）
c代码实现：
int fast_power_mod(int base, int exp, int divisor) {
int rmd = 1;
while (exp != 0) {
if (exp & 0x1)
rmd = (rmd * base) % divisor;
exp = exp >> 1;
base = (base * base) % divisor;
}
return rmd;
}type_prime miller_rabin(int num) {
//special case for small number
if (num <= 0) return ILLEGAL;
switch (num) {
case 1:
return ONE;
case 2:
case 3:
return PRIME;
default:
break;
}
//for num < 4759123141, which means all int value
const int TEST_BASE[] = {2, 7, 61}
for (int i = 0; i < sizeof(TEST_BASE) / sizeof(TEST_BASE[0]); i++) {
int base = TEST_BASE[i];
if (base >= num) return PRIME;
int exp = num - 1;
while (true) {
int rmd = fast_power_mod(base, exp, num);
if (rmd == num - 1) break;
if (rmd != 1) return COMPOSITE;
//to here means rmd==1
if ((exp & 0x1) == 1) break;
exp = exp >> 1;
}
}
return PRIME;
}
