快速Monte Carlo概率素数测试算法

Fast Monte Carlo probabilistic algorithm for primality test

为了快速实现素数测试,基于容斥原理给出了一种试除小素数优化策略,然后将该优化策略与Leh-m ann算法以及基于递归技术改进的计算余数算法相结合,提出了一种实现快速素数测试的Monte Carlo概率算法.利用该算法并结合C++6.0具有的特殊整型-int64特性,可以快速测定大奇数(至少78位十进制数)是否为素数.

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.