|
Zapiski Nauchnykh Seminarov LOMI, 1984, Volume 137, Pages 124–188
(Mi znsl4791)
|
|
|
|
This article is cited in 27 scientific papers (total in 27 papers)
Polynomial-time factoring of polynomials and finding the compounds of a variety within the aubexponential time
A. L. Chistov
Abstract:
Let $F=H(T_1,\dots,T_l)[\eta]$ where either $H=\mathbb Q$or $H$ is a finite field, $T_1,\dots,T_l$ be algebraically independent over $H$, a polynomial $\varphi\in H(T_1,\dots,T_l)[Z]$ be a minimal for $\eta$, denote $q=\operatorname{char}(F)$. Let $L(f)$ be the size of $f\in F[X_0,\dots,X_n]$.
THEOREM 1. One can factor $f$ over $F$ within the polynomial in $L(f), L(\varphi), q$ time.
The theorem expands the result of [4] treating the case of a finite $F$.
Let homogeneous polynomials $f_0,\dots,f_k\in F[X_0,\dots,X_n]$ be given and $\operatorname{deg}_{X_0,\dots,X_n}(f_i)<d$, denote bу $L$ the sise of the system $f_0=\dots=f_k=0$. The variety of common roots in $\mathbb P^n(\bar F)$ of the latter system is decomposable on irreducible compounds $W_\alpha$. A compound $W_\alpha$ is represented further by its general point and by a system of equations whose variety of roots is $W_\alpha$. The following theorem Improves bounds from [4].
THEOREM II. An algorithm is suggested finding all compounds $W_\alpha$ within polynomial in $(Ld^n)^{n+l}$, $q$ time.
Citation:
A. L. Chistov, “Polynomial-time factoring of polynomials and finding the compounds of a variety within the aubexponential time”, Computational complexity theory. Part II, Zap. Nauchn. Sem. LOMI, 137, "Nauka", Leningrad. Otdel., Leningrad, 1984, 124–188
Linking options:
https://www.mathnet.ru/eng/znsl4791 https://www.mathnet.ru/eng/znsl/v137/p124
|
Statistics & downloads: |
Abstract page: | 426 | Full-text PDF : | 557 |
|