随着信息化时代的来临,在计算机网络中信息的传输量呈现出几何级的增长,由于信息在传输过程中存在泄密的可能性,所以信息安全成为一门越来越重要的学科。为了保证网络中传输数据的安全,通常对数据进行加密,现在的常用加密体制分为对称加密体制和非对称加密体制,对称加密体制在应用中存在密钥收发安全性差、管理复杂和不能有效解决数字签名的问题。而非对称加密体制(即公钥体制)不存在上述问题,使用公钥进行加密,私钥进行解密,公钥可以公开,只须对私钥保密,便于实现数字签名和认证等功能,不断被用于军事、商业等方方面面。在非对称加密体制中,RSA公钥密码体制是目前较为完善、安全、实用的公钥密码算法,已经成为了公钥密码的国际标准,广泛应用到军事、商业当中,人们最为常见的u盾就使用了RSA加密算法。在RSA加密算法中,其安全性是基于大整数的分解问题,相对应的是寻找大素数的难题,所以快速生成符合RSA算法要求的大素数是一个具有重要意义的研究方向。在数论中,只能被自身和1整除的数称为素数。其关键问题就是给定一个大数,如何来判定这个大数是否为素数,根据定义,可以用比其小的素数去除,但是当这个数很大时,该方法不具有可操作性。所以判定一个大数是否为素数成为许多科学家所关注的问题。本论文的撰写过程中,系统了解了RSA加密算法的原理,参考了有关大素数素性判定的若干国内外文献。在系统学习了各种素数测试方法的基础上,对公钥算法中的大素数生成方法进行了改进,具体步骤为：根据梅森素数的相关理论,引出一种新的搜索方法,采用一种新的随机递增搜索替代了原来的随机搜索；在进行Miller-Rabin测试之前,结合去偶存奇和小素数表过滤进行预过滤处理,缩小Miller-Rabin测试范围,减小了Miller-Rabin测试中的幂模运算。从而加快大素数的生成时间。在一定程度上提高RSA算法的效率,具有较强的实用意义。