檢測素數的方法——O(logN)

理論上能快速檢測出絕大部分數,除了Carmichaels數。

function expmod(a,exp,m){
        if(0 == exp) return 1;
        if(exp % 2){
            return a * (expmod(a, exp-1,m) % m) % m;
        }else{
            return Math.pow(expmod(a, exp / 2, m) % m, 2) % m;
        }
    }

    function test(n){
        if(n < 2 || n > 2 && !(n % 2)) return false;

        for(var i = 0; i < 20 && i < n-1; i++){
            var a = ((n - 1) * Math.random() | 0) + 1;
            if(expmod(a,n,n) != a) return false;
        }
        return true;
    }

用erlang實現的話:

test(N) ->
            test_more(20, N, N > 1).

    test_more(_,_,false) ->
            false;
    test_more(0,_,F) ->
            F;
    test_more(C,N,true) ->
            A = random:uniform(N - 1),
            test_more(C - 1, N, xmath:pow(A, N) rem N =:= A).

其中xmath:pow是自己寫的大整數乘方算法(也是O(logN)復雜度)


所屬標簽

無標簽

25选5玩法中奖