03月17, 2010

检测素数的方法——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)复杂度)

本文链接:https://www.h5jun.com/post/检测素数的方法.html

-- EOF --

Comments