Complexity bound of absolute factoring of parametric polynomials

Построен алгоритм для абсолютной факторизации многочленов с алгебраически независимыми параметрическими коэффициентами. Он разбивает пространство параметров на попарно непересекающиеся конструктивные множества, так что абсолютная факторизация многочленов с коэффициентами в каждом множестве задается равномерно. Именно, для каждого множества имеется некоторое число $l\leqslant d$, $l$ переменных $C_1,\dots,C_l$, алгебраически независимых над основным полем $F$, и рациональные функции $b_{J,j}$ от параметров и от переменных $C_1,\dots,C_l$, такие что для всякого параметрического многочлена $f$ с коэффициентами в данном множестве существуют значения $c_1,\dots,c_l\in\overline{F}$, для которых разложение $f=\prod_jG_j$, где $G_j=\sum_{|J|}B_{J,j}Z^J$, абсолютно неприводимо. При этом $Z=(Z_0,\dots,Z_n)$ являются переменными многочлена $f$, каждое из $B_{J,j}$ является значением функции $b_{J,j}$ от коэффициентов многочлена $f$ и от $c_1,\dots,c_l$. Поле $\overline{F}$ обозначает алгебраическое замыкание поля $F$.
Количество построенных множеств не превосходит $(2d^2+1)^{2n+3d+5}$; кроме того, число арифметических операций в $F$, выполняемых алгоритмом, является экспоненциальным от числа коэффициентов $r={n+1+d\choose n+1}$ многочлена $f$ и оценивается как $d^{O(ndr^2)}$. Битовая сложность алгоритма в случае основного поля $F=\mathbb{Q}$ не превосходит $d^{O(ndr^2)}$, а в случае $F=\mathbb{F}_p$ не превосходит $\Bigl(pd^{ndr^2}\Bigr)^{O(1)}$, где $d$ – верхняя оценка степени многочлена $f$.
Алгоритм использует лемму Гензеля и элиминацию кванторов в теории алгебраически замкнутых полей. Библ. – 20 назв.