探索rsa算法中素数判定问题的研究

《探索rsa算法中素数判定问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中南大学硕士学位论文RSA算法中素数判定问题的研究姓名：周先华申请学位级别：硕士专业：交通信息工程及控制指导教师：蒋新华20051001摘要随着Intemet的迅速发展，资源共享广泛用于政治、军事、经济、电子商务以及各个领域，大量数据在网络中存储和传输。这些数据在存储使用和传输过程中，都有可能被中断、截获、篡改和伪造。因此，在传输过程中需要有网络安全措施来保护数据。本文在分析安全RSA公钥密码体制对素数的要求和现有素数判定的有关算法及其所讨论的素性的各个方面的基础上，主要研究由Bhattacharjee和Pandey提出的广义Carmiehael数的一些性质以及Kayal和S

2、anexa给出的无平方因子判定的多项式时间算法。上述两个2问题的研究使Agrawal、Kayal和Sanexa最终在2002年8月解决了“多项式时间判别素数”这一和RSA算法密切相关的世界难题，因而这些问题的研究对完善和深化RSA算法非常重要。本文通过讨论广义Carmichael数的性质，得到了一个合数一为七阶Carmichael数的充要条件。特别地，得到了二阶和三阶Carmichael数的充要条件以及一阶Carmichael数(通常意义下的Carmiehael数)为二阶Carmichael数的充要条件，并且构造了一个算法。通过此算法，证明了一阶Carmichael数和二阶C

3、armichael数互不包含，从而解决了Bhattacharjee和Pandey提出的一个未解决的公开问题。本文还给出了一个基于Fermat小定理的快速无平方因子判定的一个多项式算法。该算法在计算时间上优于Kayal和Sanexa给出的算法。关键词：信息安全，RSA算法，广义Carmichael数，素性测试算法，无平方因子Abstract晰t11therapiddevelopmentofInternet,resource-sharingis耐delyusedinthefieldssuch鹪politics．military,economy,electroniccommerce

4、andetc．AgreatdealofdataissavingandtransmittingonInternet．However,thedatamaybeinterrupted，intercepted，captured,tamperedwithandcounterfeitedduringtheprocessofsaving，usingandaausmittinginnetwork．So，safeguardingmeasuresshouldbeadoptedtoprotectdataduringthetransmissionprocessinnetwork．Thispaperi

5、sanalyzingthedemandofthesafeRSApublic-keyCryptosystemtoprimenumberandtherelevantalgorithmofthecurrentjudgingprimenumber．InthefoundationinitsavariousandeachaspectfordiscussingPrimality,wemainlystudysomepropertiesofthegeneralizedCarmichaelnumbersproposedbyBhattacharjeeandPandey,andthepolynomi

6、altimetestingalgorithmsuggestedbyKayalandSaxena,whichguaranteesthatanycompositenwhichmanagestopassthetestissquare-free．ThestudyoftheabovetwoproblemsledAgrawal，KayalandSaxenatothefinalsolutionofaworldwideproblemfortestl,-培whetheranumberisprimeornotindeterministicpolynomialtimeonAugust2002．．n

7、璩testingiscloselyrelatedtoRSAalgorithm,therefore．theaudyoftheabovetwoproblemsisagreathelptoperfectanddeepenRSAalgorithmmoreclosely．。Thearticle，bystudyingthepropertiesofthegeneralizedCarmichaelnumbers，hasobtainedthenecessaryandsufficientconditionsforacomp