有限域上方程xr=a的求解
有限域上方程求解在一些著名的公钥密码算法、二次筛法分解整数算法、椭圆曲线上点的计数及椭圆曲线素性检测中都有重要应用.在这篇文章中我们对Berlekamp在Fp上求解x2=a的随机算法进行了扩展,以用来对x3=a这样的代数方程来求解,同时利用分圆理论给出了其期望运行时间的分析.与以往的算法不同的是,我们使用二次剩余理论来对三次方程进行求解,计算的过程中并不需要寻找三次非剩余,该算法的期望运行时间为O(log2 p (loglog p))次位操作.同时我们也将这一方法扩展到对Fp上任意的三次方程即x3+ax2 +bx+c=0的求解,给出对于该方程解的个数并求得x3+ax2 +bx+c=0的所有解.另外,我们将Cipolla-Lehmer方法通过计算有限域上元素范数的方法扩展到C上方程xr=a的求解,其中r为素数幂,该算法也是随机算法.我们通过构造Fq[x]上的不可约多项式f(x),来构造我们的算法,其中deg(f) =r且f(x)的常数项为(-1)ra.同时我们利用Davenport-Hasse关系和DoubleCounting技术,给出对我们的算法分析,其期望运行时间为O(logq)次Fq上的运算.对于满足r4≤q的r,我们的算法是非常有效的.
三次根、有限域、Cipolla-Lehmer算法、分圆理论
1
TP309.7(计算技术、计算机技术)
国家973计划课题云计算及云安全的基础理论2012CB723401;国家自然科学基金A3前瞻计划项目下一代互联网安全与隐私关键性技术的研究61161140320;国家自然科学基项目61371083,61373154;信息安全协议分析新方法61033014
2016-06-13（万方平台首次上网日期，不代表论文的发表时间）
共15页
602-616
