×

An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in subexponential time. (Russian. English summary) Zbl 0561.12010

Let the field \(H\) be either \(\mathbb Q\) or a finite field \(\mathbb F_{q^{\kappa}}\) with \(q^{\kappa}\) elements, and let \(T_ 1,T_ 2,\ldots,T_ n\) be algebraically independent over \(H\). Denote \(F=H(T_ 1,\ldots,T_ n)[\eta]\), where \(\eta\) is algebraic and separable over \(H(T_ 1,\ldots,T_ n)\) with irreducible polynomial \[ \phi =\sum_{0\leq i\leq \deg_ z \phi} (\phi_ i^{(1)}/\phi^{(2)}) z^ i\in H(T_ 1,\ldots,T_ n)[z] \] \((\deg\phi^{(2)}\) is the smallest possible degree).
If \(f\in F[X_ 0,X_ 1,\ldots,X_ n]\) then \[ f=\sum_{0\leq i\leq \deg_ z\phi;\quad i_ 0,\ldots,i_ n}(a_{i,i_ 0,\ldots,i_ n}/b) \eta^ i X_ 0^{i_ 0}\cdots X_ n^{i_ n}. \] Let \(\deg_ T(f)=\max_{i,i_ 0,\ldots,i_ n}\{\deg_{T_ j}(a_{i,i_ 0,\ldots,i_ n})\), \(\deg_{T_ j}(b)\}\) and length \(\ell (h)\) of \(h\) denote the number of ciphers of \(h\), if \(h\in\mathbb Q\), or \(\ell (h)=\log_ 2q\), if \(h\in \mathbb F_{q^{\kappa}}\). Also, let \(\ell (f)=\max \{\ell (h)\mid h\in H\) is a coefficient in \(a_{i,i_ 0,\ldots,i_ n}\) or \(b\}\) and let \[ L_ 1(f)=(\max_{0\leq i\leq n}\deg_{X_ i}f+1)^{n+\ell +1} (\max_{1\leq j\leq \ell}\deg_{T_ j}f+1)^{\ell} (\deg_ z\phi +1) \ell (f). \]
Main theorem of Chapter 1: The polynomial \(f\) can be factored over \(F\) within a time polynomial in \(L_ 1(f)\), \(L_ 1(\phi)\) and q.
Let \(f_ 0,f_ 1,\ldots,f_{k-1}\in F[X_ 0,X_ 1,\ldots,X_ n]\) be homogeneous polynomials and \(\deg_{X_ 0,\ldots,X_ n^{f_ i}}<d\), \(\deg_{T_ 1,\ldots,T_{\ell},z}\phi <d_ 1\), \(\deg_{T_ 1,\ldots,T_{\ell}^{f_ i}}<d_ 2\). Denote \(L_ 2(f_ i)=\binom{d+n}{n}\cdot d_ 1 d_ 2^{\ell} \ell (f_ i)\) and \(L_ 2=\sum L_ 2(f_ i)\). The variety \(\{f_ 0=\ldots=f_{k-1}=0\}\subset P^ n(F)\) of common roots is decomposable in irreducible components \(W_{\alpha}\), which are represented further by its general points and by a system of equations such that the variety of its roots is \(W_{\alpha}\). The author has suggested an algorithm finding all components \(W_{\alpha}\) within a time polynomial in \(L_ 2\), \(d^{n^ 2}\), \(q\).
Most of the results in this paper are improvements of those by D. Yu. Grigor’ev [same volume, 20–79 (1984; see the following review Zbl 0561.12011)].

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
11Y05 Factorization
11T06 Polynomials over finite fields
68W30 Symbolic computation and algebraic computation
14A10 Varieties and morphisms

Citations:

Zbl 0561.12011