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

Fast Monte Carlo probabilistic algorithm for primality test

作　　者：贺毅朝[1] 王彦祺[1] 刘坤起[1,2] 

机构地区：[1]石家庄经济学院信息工程系,石家庄050031 [2]中国地质大学计算机学院,武汉430074

出　　处：《哈尔滨工业大学学报》2009年第9期235-237,共3页Journal of Harbin Institute of Technology

基　　金：河北省科技攻关资助项目(07216926;052135152)

摘　　要：为了快速实现素数测试,基于容斥原理给出了一种试除小素数优化策略,然后将该优化策略与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.

关 键 词：概率算法 素数测试 Lehmann算法 递归技术 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]