论文部分内容阅读
本文中我们主要对数论和密码学中出现的有限域上的一元方程求解问题和相关问题进行了探讨,主要包括有限域上的平方根计算,三次根计算,高次根计算和素性判定等问题。首先,我们给出一个确定性算法来计算有限域Fq上的平方根。我们的算法通过构造一个和Fq×Fq同构的多项式环,然后在该环上完成计算。我们算法的运行时间为O(t log t log q+log2 q),其中q-1=2st。当t=poly(log q)时,我们的算法是确定的多项式时间算法。同时我们将该算法应用到Proth素数判定中,当t为O((log q)2)时,我们的算法是目前已知的最优Proth素性判定算法。其次,我们将Sze在有限域Fq上计算平方根的确定性算法扩展为随机算法,其中q-1=2st。我们算法的期望运行时间为O((log q)2)。和TonelliShanks算法相反,我们的随机算法在s越大时,其每次随机选择成功的概率越高,相比原始的Sze算法,我们的随机算法不需要计算ζ4。再次,我们使用Lucas序列给出了有限域Fp上计算平方根的三个算法,我们先使用Vn(P,Q)直接构造了一个随机算法来计算Fp上的平方根,其期望运行时间为4.5 log p次Fp上的乘法操作。然后我们使用Vn(P,1)构造了一个确定性算法来计算有限域上的平方根,该算法恰好能对(p-1)/4+1个二次剩余计算平方根。之后我们将该确定性算法扩展成一个随机算法,其期望运行时间为2 log p次Fp上的乘法操作。再次,我们将Berlamp算法计算有限域Fq上平方根的随机算法扩展到对x3=a的方程的求解,同时使用分圆理论给出其算法分析。与以往的算法不同的是,我们使用二次剩余理论对三次方程进行求解,计算的过程中并不需要寻找三次非剩余,同时我们也将这一方法扩展到对Fq上任意的三次方程x3+ax2+bx+c=0的求解。最后,我们将Cipolla-Lehmer算法计算有限域Fq上平方根的随机算法通过计算Fq扩域Fqr上元素范数的方法扩展到对方程xr=a的求解,其中r为素数幂。我们通过构造Fq[X]上的不可约多项式f(x)给出我们的算法,其中deg(f)=r且f(x)的常数项为(-1)ra。同时我们利用Davenport-Hasse关系和Double Counting技术,给出我们构造f(x)算法的分析。对满足r4≤q的r,我们的算法是非常有效的。