Fast Monte Carlo probabilistic algorithm for primality test
Kunqi Liu · Ha'erbin gongye daxue xuebao · 2009
For the efficient testing of prime number,a try-division optimization strategy is provided based on inclusion-exclusion principle.Combined the optimization strategy and Lehmann algorithm with the algorithm of remainder calculation improved by recursion techniques,a Monte Carlo probabilistic algorithm is proposed to implement rapid primality test.Using the new algorithm and the typical integer type-int64 characteristic of C++6.0,the testing of prime number(at least 78 digital) can be implemented quickly.