论文标题
在有限场上具有固定多项式的欧几里得算法的平均案例复杂性
Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
论文作者
论文摘要
我们分析了在固定最高的多项式G时，分析了在有限的Q元素上，将单变量非恒定多项式的欧几里得算法（g，f）施加在有限的Q元素上。考虑到固定度的所有元素F，我们就Q的数量F量渐近地建立了Q渐近最佳的界限，而元素f的数量与G相对较高，并且对于GCD的平均程度（G，F）。实际实验证实了我们估计的准确性。我们还表现出渐近的最佳界限，对于上面应用于对（G，F）的欧几里得算法的平均案例复杂性。
We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field F_q of q elements when the highest-degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f which are relatively prime with g and for the average degree of gcd(g,f). The accuracy of our estimates is confirmed by practical experiments. We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.
