随着Internet的迅速发展,资源共享广泛用于政治、军事、经济、电子商务以及各个领域,大量数据在网络中存储和传输。这些数据在存储使用和传输过程中,都有可能被中断、截获、篡改和伪造。因此,在传输过程中需要有网络安全措施来保护数据。 本文在分析安全RSA公钥密码体制对素数的要求和现有素数判定的有关算法及其所讨论的素性的各个方面的基础上,主要研究由Bhattacharjee和Pandey提出的广义Carmichael数的一些性质以及Kayal和Sanexa给出的无平方因子判定的多项式时间算法。上述两个问题的研究使Agrawal、Kayal和Sanexa最终在2002年8月解决了“多项式时间判别素数”这一和RSA算法密切相关的世界难题,因而这些问题的研究对完善和深化RSA算法非常重要。 本文通过讨论广义Carmichael数的性质,得到了一个合数n为k阶Carmichael数的充要条件。特别地,得到了二阶和三阶Carmichael数的充要条件以及一阶Carmichael数(通常意义下的Carmichael数)为二阶Carmichael数的充要条件,并且构造了一个算法。通过此算法,证明了一阶Carmichael数和二阶Carmichael数互不包含,从而解决了Bhattacharjee和Pandey提出的一个未解决的公开问题。 本文还给出了一个基于Fermat小定理的快速无平方因子判定的一个多项式算法。该算法在计算时间上优于Kayal和Sanexa给出的算法。