AKS算法对现代密码学的影响.pdf

≯#瓣≮ 讳}十**疗 AKS算法对现代密码学的影响 刘永亮1姚鸿勋1高文“2 (哈尔滨工业大学计算机科学与工程系，哈尔滨150001) z(中国科学院计算技术研究所，北京100080) E——mail：yllin@cti．corn．en Saxena提出了一个称为AKS的算法。 AgrawaI、NeerajKayal和Nitin 摘 要 最近，印度的三个计算机抖学家Manindra 笔者使用这个算法证明了可在多项式时问内对一个整教是否为素敷进行确定性的判定，从而解袭了一个古老的教学问 题。这个结果对于数论和计算-J／．杂性理论的研究与发展具有重要意义。由于现代密码学正是建立在整数分解理论和计算 复杂性理论的基础之上，因此这个算法叶现代密码学的影响引起了A,f11的关注。谊文将就此进行阐述。 关键词AKS算法现代密码学RSA算法 6 文献标识码A 中围分类号TP301 文章编号1002—8331一(2003)11_000l一03 TheEffectofAKS onModem Algorithm Cryptography Liu Yao GaoⅥknl。2 Hongxunl Yonglian91 Instituteof of Science．Harbin 150001) 1(DepartmentComputer Technology，Harbin of 0f 100080) 2(Institute AcademySciences，Beijmg ComputingTechnology．Chinese inIndia art scientistsManindra andNitinSaxena Abstract： Agrawal．Nee飓jKayal present Recently，threecomputer thatit is todetermineifanumberis 8 in caned this 8 possible prime algorithmAKS．By algorithmtheygive proof has to havecrackedan mathematicalTheresult research polynomialtime．So，they age-old problem importantpignificance inbe