论文部分内容阅读
素数的研究已有很长的历史,现代密码学的兴起给它注入了新的活力,提出了新的课题,其中最重要的就是素数判定。在已知的公钥密码系统中,RSA公钥密码体制和椭圆曲线密码体制(ECC)是两个最具有代表性,同时也是最有发展前途的公钥密码体制。RSA公钥密码体制是建立在选择大素数p、q的基础上的,椭圆曲线密码体制中选取椭圆曲线时也要求曲线的阶是大素数或者具有大素数因子。素数的选择直接影响着密码体制的安全性,因此,正确判断一个数是否为素数是密码体制中的一个非常重要的环节。
本文首先对素性检测的研究背景、意义以及国内外发展趋势进行了简要的分析和综述。其次,介绍了素性检测方面的基础理论以及目前存在的几种常用素性检测算法,探讨了二次型及二次域的相关理论知识。第三,简要介绍了椭圆曲线的相关知识,同时详细探讨了将椭圆曲线运用到素性检测领域的研究,即椭圆曲线素性检测算法,并在此基础上简要介绍了ECPP(Elliptic Curve Primality Proving)算法实现过程中的相关内容。第四,在GK算法的基础上将其推广,得到了一个利用多点阶的椭圆曲线素性检测的改进算法——广义GK算法,此算法在应用上比GK算法更有效,具有更广泛的实用价值。按照这一推广思想,其它的几种运用椭圆曲线的素性检测算法(the basic ECPP algorithm、the fast version of ECPF)也可进行相应的改进。最后,对全文所做的主要工作和不足进行总结,对以后更进一步的研究进行展望。