有限域上方程xr=a的求解

• 作者: 曹珍富 李哲 董晓蕾
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 三次根 有限域 Cipolla-Lehmer算法 分圆理论
• 年，卷（期）: 2014,（6）
• 页码范围: 602-616
• 页数: 15页
• 分类号: TP309.7
• 字数: 8955字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000055

摘要

有限域上方程求解在一些著名的公钥密码算法、二次筛法分解整数算法、椭圆曲线上点的计数及椭圆曲线素性检测中都有重要应用.在这篇文章中我们对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,我们的算法是非常有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李哲	上海交通大学计算机科学与技术系	7	176	4.0	7.0
2	曹珍富	华东师范大学上海市高可信计算重点实验室	18	147	4.0	12.0
3	董晓蕾	华东师范大学上海市高可信计算重点实验室	16	140	4.0	11.0