第21卷第3期
2004年9月
广东工业大学学报
Journal of Guangdong University of Tedmology
Vo1．21 No．3
Septemt~r 2004
AKS算法及其在公钥加密术中的意义
赵 勇‘，张益新‘，杨文伟
(1．广东工业大学计算机学院，广东广州510090；2．广东工业大学 网络信息中心，广东广州510090)
摘要：AKS算法是3位印度的计算机科学家于2002年8月提出的，它是一个能在输入规模的多项式
时间内确定的对一个数进行素性测试的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
．本文详细介绍了AKS算法的基本思想、算法流程以及
时问复杂度的分析．又由于大素数的选取在公钥加密术中极为重要，因此讨论了AKS算法在公钥加
密术中的意义．
关键词：AKS算法；RSA算法；公钥加密术
中图分类号"TP301．6 文献标识码：A 文章编号：1007—7162(2004)03．0079．04
素数在数学特别是在数论中具有非常重要的地位．研究素数的性质具有很高的应用价值，
尤其是素数的那些可以用来对其进行素性测试的性质更是如此．如在密码学的公钥加密术中就
需要找出两个100多位的大素数．而高效地判断一个数是否为素数，从古至今都是一个令数学
家们着迷和困惑的问题．
一 直以来人们所采用的进行素性测试的方法，都有这样或那样的缺陷．最古老的方法当推
古希腊的Eratosthenes筛法，它是一个确定的、对所有数n都有效的素性测试的方法，但其所需
的时间复杂度为D(√n)，为n大小的幂次方，因而效率极低，不能在实际中应用．而一个有效的
素性测试方法只应花费logn的多项式时间(n为待测试数)．17世纪的Fennat小定理指出了素
数的一个性质：n为素数且(n，a)=1，则：
a一 =1(modn) (1)
成立．由之产生了一些有效的素性测试算法．但由于Fennat小定理的逆定理不成立，即存在一些
合数n，使得当(n，a)=1时，等式(1)也成立．事实上，当n为随机产生的一个100位合数，其
满足等式(1)的几率为l0 ．1975年提出的Miler—Rabin法是具代表性的一种基于Fennat小定理
的改进型算法，它接受Extended Riemann假设，可以以小于2。即的错误概率判断一个给定数的素
性，甚至可以检出能通过费马测试的Carmiehael数．1983年，Adleman、Pomeranee和Rumely提出的
用于素性测试的确定算法被认为是这一领域的重大突破，但该算法的时间复杂度为
(1ogn) 0glosn ，且在某种意义上该算法是从Miller的算法思想中演变而来．1986年，Goldwasser
和Kilian提出一个基于椭圆曲线的算法，该算法在满足一个广泛认可的假设的前提下，可以在
给定数位数的平均多项式时间内对其完成测试．之后，该算法又得到进一步改善．⋯
上面介绍的所有算法，有的能确定的判断一个数的素性，但其时间复杂度是待检测数大小
的指数函数而不适合在实际中应用；有的能非常快速地对一个数进行素性测试，但会以很小的
概率产生一个错误结论；有的虽也是属于快速的素性测试方法，但使用了未证明的假设．因而，
收稿日期：2003．05．05
作者简介：赵勇(19r77．)，男，在读研究生，主要研究方向为网络软件与多媒体技术
维普资讯 http://www.cqvip.com
80 广东工业大学学报 第2l卷
寻求一种能在可被接受的时间复杂度内的，不基于任何假设的，确定的对一个给定数进行素性
测试的有效算法对计算机科学工作者和数学工作者来说，都是一个巨大的挑战．2000多年来，
研究者们尝试了很多方法，也使用了一些复杂的数学技术，但没有一个成功．
直到2002年8月，印度的Manindra Agrawal教授和他的两个学生Neeraj Kayal、Nitin Saxena设
计了一种被称为AKS的素性测试算法，该算法能够在多项式时间内对给定数的素性进行确定
性判定，而且不基于任何假设，因此被认为是这一领域的一个重大突破．学术界认为这一算法将
产生广泛的影响，而最直接的就是对整数理论和计算复杂性理论的影响．由于现代密码学中的
公钥加密术正是以整数分解理论和计算复杂性理论为基础，因此AKS算法对公钥加密术中的
大素数确定算法将产生巨大影响，也在此方面引起了人们的关注．
1 AKS算法基本思想
AKS算法是以一个从Fermat小定理派生出的恒等式为理论基础的，该等式可描述如下：
令a∈Z，n∈N，并且(a，n)=1．则 n是素数，当且仅当：
(X+a) = +a(modn) (2)
成立．
证明：对于 (0<
1．
1)如果存在a，b(a∈N，b>!)使得n=a ，则n为合数．
2)找出最小的r使得0，(H、>4log2 n．
3)如果对一些a≤r，使得1<(a，n)<／'t成立，则／'t为合数．
维普资讯 http://www.cqvip.com
第3期 赵 勇，等：AKS算法及其在公钥加密术中的意义 8l
4)如果凡≤r，则凡为素数．
5)Fora、=1 to 2、俩 logn do
如果( +a) ≠ +a(modXr一1，凡)，则凡为合数；
6)凡为素数；
上述算法流程中，h(r)为Euler’S totient function，它返回小于r并与r互质的数的个数．对于
r∈N，凡∈Z并且(a，凡)：1，O (凡)表示凡模r的阶，即是使凡 =1(mod r)成立的最小k值．
可见，AKS算法过程简单明了．其最关键的部分在于第2步——找出一个r．至于为什么使
O (凡)>41 凡成立的最小的r满足条件，详细说明请看参考文献[2]．
3 AKS算法复杂度分析
AKS算法中引入了O (t(凡))表示O(t(凡)·poly(1og t(凡)))，其中t(凡)表示任意关于凡的
函数．例如，O (1og 凡)：O(1og 凡·poly(1og logn))．
AKS算法流程中第1步的时间复杂度约为O一(1og3凡) ]．在第2步找到一个r使得O (凡)
>41 凡．AKS算法尝试连续的r值，检验是否对每一个k~<41og2凡，式凡 ≠1(mod r)都成立．对
一 个特定的 r，需要花费时间 O (1o 1／,log r)．并且，只需测试 D(1o 凡)个不同的 r即可 ．因
此，第2步的时间复杂度为O (1o 凡)．
第3步需要计算r的最大因子，每个最大因子计算需要花费时间O(1og凡) ]．因而，此步所
需时间为 O(rlogn)=O(1og6凡)．
第4步仅需时间O(1og凡)．
第5步需要验证2√h(r)log凡个方程式．每个方程式的验证可在 O一(rlog2凡)步内完成．
因此，此步耗费时间O (r lo 凡)=O (r1．5lo 凡)=O一(1og 凡)．
第5步的时间复杂度决定了整个AKS算法的时间复杂度，即AKS算法的时间复杂度为O一
(1og 凡) ．
在接受两个猜想——Artin猜想和Sophie．Gennain素数密度猜想的前提下，通过改善评估 r
的方法，可以使AKS算法的时间复杂度达到最小——O一(1og6凡)．
4 AKS算法与公钥加密术
4．1 公钥加密术中大素数选取的意义
我们以公钥加密术中应用最广的RSA算法为例进行说明．
RSA算法的安全基础源于一个假设——大数的分解质因数是NP完全问题．例如，将一个
512位的二进制数分解质因数用最强计算机要几百年．它的数学基础是，对于两个不同素数之
积／7,，有公式 ，= ， (modn)成立( ，，，均为整数)．特例：当Y：1(modh(／7,))时， ，=
(modn)．由此产生的RSA算法过程如下：
1)产生两个大素数P，q
凡 P。q；
h(凡)=(P一1)(q一1)．
2)随机选取e，使得(e，h(凡))=1，则即为公钥
3)用Euclidean算法求出e关于模h(凡)的乘法逆，则即为私钥
维普资讯 http://www.cqvip.com
82 广东工业大学学报 第21卷
4)公开公钥，保密私钥，P和q应销毁
5)加密消息 m时，计算 c：m (modn)，c即为密文
6)解密密文c时，计算 m=c (modn)，m即为明文
由于d·e=1(modh(n))，因此RSA可从密文解密得到明文，算法可行 ．
在加密消息m时，对m的e次幂运算可以在O(1oge)时间内完成．因此，能否在可接受的时
间复杂度内找到两个大素数P和q，决定了RSA算法能否应用于实际．
4．2 AKS算法对RSA算法的影响
目前在RSA算法中确定大素数的方法是在适当的范围内选取一些奇数，然后用 Miler．Rabin
法对其进行素性测试．Miler．Rabin法可以在O(1ogn)时间内判定输入n的素性，但其会以一个
很小的概率出错．一旦该种情况出现，RSA算法失败，即使解密不能正确执行或使他人可以用比
预计少得多的时间打破加密术——算出私钥．但由于此概率极小，在人们可接受的范围之内，因
而RSA公钥加密术仍广泛应用于各个领域．
AKS算法的出现，使这一情况发生了改变．AKS算法可以在输入规模的多项式时间内确定
地判断一个数的素性．目前已有多种实现了AKS算法的C++程序，因此将其应用于实际是可能
的．但AKS算法的时间复杂度为O～(1og n)，仍远远高于Miler．Rabin法的O(1ogn) J．因此在
很多比较注重效率的应用中，Miler-Rabin法仍更具吸引力．但另一方面，在一些安全性高于一切
的应用领域(如：银行，电子政务，安全通信等)，AKS算法在理论上使得公钥加密术无懈可击，并
且在实践上也具有可操作性．而且AKS算法在满足某些假设的前提下，性能会大大提高，其时
间复杂度可以达到O一(1og n)，甚至O～(1og n)．因此，我们可以说AKS算法改善了公钥加密术
的安全性．随着计算机计算能力的提高和AKS算法本身的改进，其有望应用于RSA算法中的素
性测试．
5 结论
AKS算法简单、优雅，以简单的代数知识解决了人们2000多年来孜孜以求的数学难题——
在输入规模的多项式时间内确定地判断一个数的素性．虽然其比现在广泛使用的素性测试方法
速度慢很多，暂时还不能得到实际的应用．但是，目前和将来会有很多的研究者致力于 算
法的改进工作，以减少其在时间方面的花费，而且计算机的计算能力也在大幅度提升．可以预
见，不远的将来，在对安全性能要求较高的领域，AKS算法将会被用来在公钥加密术中进行素性
判定．
参考文献：
[1]冯登国．密码分析学[M]．北京：清华大学出版社，2000．
[2]Manindra Agrawal，NeerajKayal，NitinSaxena．PRIMES is in P．[EB／OL]．http：／／www．cse．iitk．ac．in／news／ pfimality-v3．
paf．2003—04-28．
[3]戴华．矩阵论[M 北京：科学技术出版社，2001．
[4]Salom aaA著．公钥密码学[M]．丁存生，单炜娟，译．北京：国防工业出版社．2000．183—204．
(下转第93页)
维普资讯 http://www.cqvip.com
第3期 柳和气，等：沥青路面抗滑技术研究
[4]游蓉，张荣华．沥青混凝土路面施工工艺对面层平整度影响的分析[J]．中国市政工程，2O03，(1)：8
Study of Skid Resistance Technology for Asphalt Pavement
LIU He-qi ，LUO Zhi．qi
(1．Guangdong Provincial Expressway Limited Corporation，GlIangd10II 510100，China；
2．Faculty of Construction，Guangdong University of Technology，Gua~ oLi 510090，China)
Abstract：Combined with the skid resistance study and practice of the highway asphalt pavement in our
country，the in仃Hence factors of the skid resistance property of the asphalt pavement are discussed．Accord—
ing to the conditions that must have asphalt pavement skid resistance。the ways of to enhance the skid re．
sistance property of the asphalt pavement ale analyzed，and the construction requirement of the skid resis．
tance surface ofthe asphalt pavement are presented．
Key words：asphalt pavement；skid resistance；construction
(上接第82页)
AKS Algorithm and It’S Effect on Public—key Eneryption
ZHAO Yong ，ZHANG Yi．xin 。YANG Wen．wei
(1．Faculty of Computer，Guangdong University of Technology，cI舢 h0u 510090，China；
2．Network Information Center，Guangdong University ofTechnology，GumC~ou 510090，China)
Abstract：AKS algorithm Was proposed by three computer scientists in India in Aug 2002
．This algorithm
Call unconditionally determine whether an input number is a prime in polynomial time
． In this paper。the
basic idea，the algorithm and the time complexity analysis of AKS algorithm ale described in detail
． The
impact of this algorithm on public-key encryption is discussed because the selection of a big prime is very
important to it．
Key words：AKS algorithm；RSA algorithm；public—key encryption
维普资讯 http://www.cqvip.com
浙公网安备 33021202002483