构造了一个新的求解有限域上两个多元多项式最大公因式(Greatest Common Divisor,GCD)的算法。研究过程中,设K为一个有限域,A,B∈K[x_(1),x_(2),…,x_(n)],A与B的最大公因式G=gcd(A,B)。通过引入一个新变元y将n元多项式GCD问题转化为n+...构造了一个新的求解有限域上两个多元多项式最大公因式(Greatest Common Divisor,GCD)的算法。研究过程中,设K为一个有限域,A,B∈K[x_(1),x_(2),…,x_(n)],A与B的最大公因式G=gcd(A,B)。通过引入一个新变元y将n元多项式GCD问题转化为n+1元关于变元y分离的GCD问题,然后进行n+1次赋值和n+1次单变元的GCD计算,再通过计算不同赋值前后的系数以及求解离散对数问题进而确定G的每一项,最后求解出G。此外,给出了一种有限域上求解多元多项式GCD的算法,并用一个例子来进一步展现算法的流程。最后,对该算法的复杂度做了简单的分析。该算法的复杂性与最大公因式G的项数紧密相关,是一个稀疏型的算法,因而主要适用于G的项数不是太多的情形。展开更多
文摘构造了一个新的求解有限域上两个多元多项式最大公因式(Greatest Common Divisor,GCD)的算法。研究过程中,设K为一个有限域,A,B∈K[x_(1),x_(2),…,x_(n)],A与B的最大公因式G=gcd(A,B)。通过引入一个新变元y将n元多项式GCD问题转化为n+1元关于变元y分离的GCD问题,然后进行n+1次赋值和n+1次单变元的GCD计算,再通过计算不同赋值前后的系数以及求解离散对数问题进而确定G的每一项,最后求解出G。此外,给出了一种有限域上求解多元多项式GCD的算法,并用一个例子来进一步展现算法的流程。最后,对该算法的复杂度做了简单的分析。该算法的复杂性与最大公因式G的项数紧密相关,是一个稀疏型的算法,因而主要适用于G的项数不是太多的情形。
