素数构造和判定算法研究综述  

作　　者：周利荣[1] 胡天磊[2] 

机构地区：[1]衢州职业技术学院信息工程学院,浙江衢州324000 [2]浙江大学计算机科学与技术学院,杭州310007

出　　处：《电脑编程技巧与维护》2019年第8期9-12,共4页Computer Programming Skills & Maintenance

基　　金：衢州职业技术学院重点科研项目,项目编号:QZYZ1705

摘　　要：分析了用于素数构造和判定的相关定理及常用的算法:Miller-Rabin素数测试算法、基于莱梅定理的素数构造算法、AKS素数测试算法及3种改进算法。对Miller-Rabin素数测试算法、基于莱梅定理的素数构造算法、AKS素数测试算法的效率进行了比较。实验数据表明,Miller-Rabin素数测试算法的效率最高,基于莱梅定理的素数构造算法次之,AKS素数测试算法及3种改进算法效率最低。

关 键 词：二次探测定理 莱梅定理 AKS定理 有限域 

分 类 号：O15[理学—数学]