有限域上一元方程求解和相关问题的分析

《有限域上一元方程求解和相关问题的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据万方数据万方数据万方数据万方数据上海交通大学硕士学位论文摘要有限域上一元方程求解和相关问题的研究摘要本文中我们主要对数论和密码学中出现的有限域上的一元方程求解问题和相关问题进行了探讨，主要包括有限域上的平方根计算，三次根计算，高次根计算和素性判定等问题。首先，我们给出一个确定性算法来计算有限域Fq上的平方根。我们的算法通过构造一个和Fq×Fq同构的多项式环，然后在该环上完成计算。我们算法的运行时间为Oe(tlogtlogq+log2q)，其中q−1=2st。当t=poly(logq)时，我们的算法是确定的

2、多项式时间算法。同时我们将该算法应用到Proth素数判定中，当t为Oe((logq)2)时，我们的算法是目前已知的最优Proth素性判定算法。其次，我们将Sze在有限域Fq上计算平方根的确定性算法扩展为随机算法，其中q−1=2st。我们算法的期望运行时间为Oe((logq)2)。和Tonelli-Shanks算法相反，我们的随机算法在s越大时，其每次随机选择成功的概率越高，相比原始的Sze算法，我们的随机算法不需要计算ζ4。再次，我们使用Lucas序列给出了有限域Fp上计算平方根的三个算法，我们先使用Vn(P,Q

3、)直接构造了一个随机算法来计算Fp上的平方根，其期望运行时间为4.5logp次Fp上的乘法操作。然后我们使用Vn(P,1)构造了一个确定性算法来计算有限域上的平方根，该算法恰好能对(p−1)/4+1个二次剩余计算平方根。之后我们将该确定性算法扩展成一个随机算法，其期望运行时间为2logp次Fp上的乘法操作。再次，我们将Berlamp算法计算有限域Fq上平方根的随机算法扩展到对x3=a的方程的求解，同时使用分圆理论给出其算法分析。与以往的算法不同的是，我们使用二次剩余理论对三次方程进行求解，计算的过程中并不需要寻找

4、三次非剩余，同时我们也将这一方法扩展到对Fq上任意的三次方程x3+ax2+bx+c=0的求解。最后，我们将Cipolla-Lehmer算法计算有限域Fq上平方根的随机算法通—i—万方数据有限域上一元方程求解和相关问题的研究上海交通大学硕士学位论文r过计算Fq扩域Fqr上元素范数的方法扩展到对方程x=a的求解，其中r为素数幂。我们通过构造Fq[X]上的不可约多项式f(x)给出我们的算法，其中deg(f)=r且f(x)的常数项为(−1)ra。同时我们利用Davenport-Hasse关系和DoubleCounting

5、技术，给出我们构造f(x)算法的分析。对满足r4≤q的r，我们的算法是非常有效的。关键词：平方根有限域确定性算法随机算法—ii—万方数据上海交通大学硕士学位论文ABSTRACTResearchofUnivariateEquationsoverFiniteFieldsandSomeRelatedProblemsABSTRACTInthisthesis,wearemainlyinterestedinsolvingunivariatepolynomialequationsoverfinitefieldsandrelated

6、problemsthatariseinnumbertheoryandcryptography.Theproblemsweareinterestedinincludesquareroot,cubicroot,r-throotandprimal-itytesting.First,wepresentadeterministicalgorithmtocomputesquarerootoveranyfinitefieldsFq.Oursquarerootalgorithmisfinishedbyconstructingaring

7、whichisisomor-phismFq×Fq.Allthecomputationsproceedsonthisring.TherunningtimeofouralgorithmsisOe(tlogtlogq+log2q)，whereq−1=2st.Ouralgorithmisdetermin-isticpolynomialalgorithmwhent=poly(logq).Also,weappliedthissquarerootalgorthmtoProthprimenumbertesting.Ouralgo

8、rithmisthebestProthprimenumbertestingalgorithmwhentisOe((logq)2).Then,weextendSze’sdeterministicsquarerootalgorithmoverFqtoarandomizedsquarerootalgorithm,whereq−1=2st.Theexpectedrunningti