A new algorithm is presented for computing the largest degree invariant factor of the Sylvester matrix (with respect either to $x$ or $y$) associated to two polynomials $a$ and $b$ in $\mathbb F_q[x,y]$ which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires $O((de)^{1+\epsilon}\log(q) ^{1+o(1)})$ bit operations, where $d$ an $e$ respectively bound the input degrees in $x$ and in $y$. It follows that the same complexity estimate is valid for computing: a generator of the elimination ideal $\langle a,b \rangle \cap \mathbb F_q[x]$ (or $\mathbb F_q[y]$), as soon as the polynomial system $a=b=0$ has not roots at infinity; the resultant of $a$ and $b$ when they are sufficiently generic, especially so that the Sylvester matrix has a unique non-trivial invariant factor. Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra $\mathbb F_q[x,y]/\langle a,b \rangle$. By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.
翻译:为计算Sylvester 矩阵的最大变数因数(美元或美元)提供了一个新的算法,该算法用于计算与两个没有非三边共同对数的多面体F_q[x,y]美元相关的两个多面体美元和美元美元。该算法由蒙特卡洛类型随机排列,需要美元(de)=1 ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ log(q) ⁇ 1+1+o(1)}美元(美元)比特操作,其中美元分别以美元和美元构成输入度。因此,相同的复杂估计对于计算是有效的:一个消除理想的$\langle a,b\rangle\ cap\ cap\mathbf F_q[x] (或$\mathbf_q[y]美元) 的生成者,只要多面体系统 $a=b=0=美元在精确度上没有根基数;当一个美元和美元的结果,当它们足够普通时, 以美元为基数的计算值计算:一个消除理想的公式,特别是Sylexbral 的基质的基质方法, 将我们最小的基质问题压成为最小的基数。