素数测试的基础是费马小定理：

对于素数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;
}