素数判断算法综述与程序实现  

Summary and Program Realization of Prime Number Judgment Algorithm

作　　者：吕橙[1] 李敏杰[1] LV Cheng;LI Min-jie(Department of Computer Science and Technology,Beijing University of Civil Engineering and Architecture,Beijing 100044)

机构地区：[1]北京建筑大学计算机系,北京100044

出　　处：《现代计算机》2020年第19期35-39,共5页Modern Computer

摘　　要：素数的判定一直是数论研究的热点之一,尤其是大数的素数判断也是密码学的基础。对素数判定算法进行综述,详细介绍朴素判别法、埃拉托斯特尼筛选法、高效判别法、费马小定理、欧拉筛选法、米勒拉宾测试法等,并给出C语言的程序代码模板。The judgement of prime number has always been one of the hot topics in number theory research,especially the prime number judgment of large numbers is also the foundation of cryptography.In this paper,the algorithms of prime number determination are reviewed,including trial division,the Sieve of Eratosthenes,Efficient discriminant method,Fermat’s little theorem,Euler Theorem,Miller_Rabbin test,etc.the program code template of C language is given.

关 键 词：素数判断 朴素判别法 埃拉托斯特尼筛选法 高效判别法 费马小定理 欧拉筛选法 米勒拉宾测试法 

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