隨機算法快速判斷質數 O( lg V )

對因數分解困惑的時候剛好經過這個文章:
如何快速验证一个超大的数为质数 - SegmentFault
以前是聽過麻煩的 Miller-Rabin偽素數檢驗法，倒是沒聽過除此之外有這麼簡潔的隨機算法可以快速判斷是否質數。原理是根據 Fermat's little theorem： a ^ ( p - 1 ) = 1 ( mod p )，對於任意 a滿足，若且唯若 p為質數。
因此隨機測試 a，是否依然滿足。而文章裡表示 Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani 這本書提到，這個算法失敗的機率約為 2^-n，n為測試的次數。所以大概可以猜想如果 p不是質數，有大約一半的機率會滿足吧( ? )，希望有空可以看看那本書。
以下是輕巧的實現，測試網址
http://zerojudge.tw/ShowProblem?problemid=a007

#include <bits/stdc++.h>
using namespace std;

vector< int > small_prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
                              47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

int int_pow_mod( int v, int p, int mod ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * v % mod;
        p >>= 1;
        v = 1LL * v * v % mod;
    }
    return res;
}

bool is_prime( int x ){
    if( x <= 101 ){
        for( int p : small_prime )
            if( x == p ) return true;
        return false;
    }
    for( int i = 0; i < 20; ++i ){
        int rnd = rand() % ( x - 2 ) + 2; // [ 0, x - 3 ] -> [ 2, x - 1 ]
        if( int_pow_mod( rnd, x - 1, x ) != 1 )
            return false;
    }
    return true;
}

int X;

void solve(){
    if( is_prime( X ) )
        cout << "質數\n";
    else
        cout << "非質數\n";
}

int main(){
    ios::sync_with_stdio( false );
    cin.tie( 0 ), cout.tie( 0 );
    while( cin >> X ) solve();
    return 0;
}