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

最近,印度的三个计算机科学家ManindraAgrawal、NeerajKayal和NitinSaxena提出了一个称为AKS的算法。笔者使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定,从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意义。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上,因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。

AKS素性测定算法的一个改进版本在PC上的实现

AKS算法从理论上成功解决了在多项式时间内进行确定性素性测定的著名难题,但它并不实用,从而得到一系列的改进。为深入分析现有AKS改进算法的实际应用效率,利用Delphi-Pascal语言在微机Pentium IV/1.8G上实现了AKS算法的一个Bernstein改进版本(简称AKS-Bernstein第二算法),并分析比较了AKS算法现有几个版本的实际耗时。对于原先需要几十甚至几千个小时才能完成一次素性测定的数据,利用AKS-Bernstein第二算法进行测试仅需几十秒,从而指出该算法比其他版本有很大改进。此外,通过分析AKS-Bernstein第二算法仍然存在的一些不足,指出该算法在素性测定的实际运用上还有待进一步完善。

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

文中简要介绍了数据加密技术的发展,对于DES,RSA及Rijndael技术进行了较为详细的论述。并提出了一种基于RSA和AES的混合密码体制,引入一个新的算法AKS及其对于加密技术的影响。针对素数测试的新算法AKS,讨论了其优缺点并阐述了它对于加密技术的影响。将它应用于加密算法,虽然运行时间还远远不能达到要求,但可以把它作为视安全性为第一位的一种新的尝试。

AKS算法及其在公钥加密术中的意义

AKS算法是3位印度的计算机科学家于2002年8月提出的,它是一个能在输入规模的多项式时间内确定的对一个数进行素性测试的方法.本文详细介绍了AKS算法的基本思想、算法流程以及时间复杂度的分析.又由于大素数的选取在公钥加密术中极为重要,因此讨论了AKS算法在公钥加密术中的意义.

基于改进C-W节约算法的成品油二次配送优化研究

成品油二次配送是成品油销售的重要环节,配送中心要实现最经济、最快速的多客户需求响应,就需要对路线、车辆、载重、时间窗等要素进行合理优化。文章针对成品油配送的特点,构造了具有载重、时间窗、访问机制等约束条件限制的调度优化模型,运用AK算法思想对传统C-W节约算法进行了改进,算例验证表明了改进算法的优越性。最后,对空车驰返问题进行了绕点折返优化,使模型得以更加完善。进一步的算例验证结果显示改进模型在成品油二次配送优化中效果极好。

一种解决配送规划问题的改进节约算法

车辆优化调度问题(VSP)是物流配送中广泛存在的一类问题,VSP问题属于NP-困难问题。在描述了简单VSP模型的基础上,对启发式算法中的C-W节约算法进行改进,将AK算法的思想运用其中,使计算结果的优化程度明显提高。

雅克比和素性判别方法的软件实现

给出了一种确定性素性判别方法——雅克比和素性判别方法的软件实现,并对其中最关键的多项运算给出了一种快速算法。同时,通过对另一种确定性素性判别方法——AKS算法的存储复杂度的分析,指出AKS算法在PC机上实现的各种困难。最后给出了雅克比和素性判别算法在奔腾IV 1.8 G上的实现结果。