AKS-Bernstein算法的非完备性及其若干新扩展

摘要：

　　AKS是第一个多项式时间的确定型素性测定算法。为了进一步提高AKS素性测定的效率，本文首先通过反例指出了AKS-Bemstein扩展算法的非完备性，并且通过分析指出Bernstein把条件增强到n是模r原根无助于提高有限扩域的维数估计值，即无法实质性加速素性测定。然后在有限商环的模xr-1多项式剩余类上对AKS算法进行了扩展，解决了有限扩域的维数估计难题，提出了重要参数r的选择策略，在此基础上提出若干AKS扩展定理，从而可以加快索性测定的速度并且避免了AKS-Bernstein算法的非完备性。

关键词： 素性测定算法 非完备性 有限扩域 维数估计

作者: Wang Zehui 王泽辉 Zhang Zhi-Guo 张治国

作者单位: Department of Scientific Computation and Computer Applications,Sun Yat-sen University,Guangzhou,5102 中山大学科学计算与计算机应用系 广州 510275 Department of Computer Science,Sun Yat-sen University,Guangzhou 510275 中山大学计算机科学系,广州 510275

会议类型: 国内会议

会议名称: 中国密码学会2009年会

会议地点: 广州

会议语种:中文

页码: 64-73

在线出版日期: 2009-11-14（万方平台首次上网日期，不代表论文的发表时间）