×

Fast parallel absolute irreducibility testing. (English) Zbl 0599.68038

We present a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility, that is irreducibility over the complex numbers. More precisely, we establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible complex factor of a multivariate integral polynomial. However, the coefficients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. A consequence of our algorithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolute irreducible integral polynomial modulo p, the polynomial’s irreducibility closure of the finite field of order p is not preserved.

MSC:

68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
12E05 Polynomials in general fields (irreducibility, etc.)
12D05 Polynomials in real and complex fields: factorization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Borodin, A.; von zur Gathen, J.; Hopcroft, J., Fast parallel matrix and GCD computations, Inf. Control, 52, 241-256 (1982) · Zbl 0507.68020
[2] Borodin, A.; Cook, S.; Pippenger, N., Parallel computation for well-endowed rings and space-bounded probabilistic machines, Inf. Control (1985), (in press) · Zbl 0598.68043
[3] Cook, S. A., Towards a complexity theory of synchronous parallel computation, Enseign. Math., 27, 99-124 (1981) · Zbl 0473.68041
[4] Davenport, J.; Trager, B., Factorization over finitely generated fields, Proc. 1981 ACM Syrup. Symbolic Algebraic Comp., 200-205 (1981)
[5] Dicrescenzo, C.; Dural, D., Computation on curves. Proc. EUROSAM 1984, Springer Lec. Notes Comp. Sci., 174, 100-107 (1984)
[6] von zur Gathen, J., Parallel algorithms for algebraic problems, Proc. 15th ACM Symp. Theory of Comp., 17-23 (1983)
[7] von zur Gathen, J., Factoring sparse multivariate polynomials, Proc. 24th IEEE Symp. Fotmtlations Comp. Sci., 172-179 (1983)
[8] von zur Gathen, J.; Kaltofen, E., A polynomial-time algorithm for factoring multivadate polynomials over finite fields. Proc. 1983 Internat. Conf. Automata, Languages, Prog, Springer Lec. Notes Comp. Sci., 154, 250-263 (1983)
[9] Heintz, J.; Sieveking, M., Absolute primality of polynomials is decidable in random polynomial time in the number of variables. Proc. 1981 Internat. Conf. Automata, Languages, Prog, Springer Lec. Notes Comp. Sci., 115, 16-28 (1981)
[10] Ibarra, O. H.; Moran, M.; Rosier, L. E., A note on the parallel complexity of computing the rank of order \(n\) matrices, Inf Proc. Lett., 11, 162 (1980)
[11] Kaltofen, E., A polynomial-time reduction from bivariate to univariate integral polynomial factorization, Proc. 23rd IEEE Symp. on Foundations of Comp. Sci., 57-64 (1982)
[12] Kaltofen, E., Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SlAM J. Comp., 14, 469 (1983) · Zbl 0605.12001
[13] Kaltofen, E., Effective Hilbert irreducibility. Proc. EUROSAM 1984, Springer Lec. Notes Comp. Sci., 174, 277-284 (1984)
[14] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001
[15] Lipson, J. D., Elements of Algebra and Algebraic Computing (1981), Addison Wesley: Addison Wesley Reading, Massachusetts · Zbl 0467.12001
[16] Loos, R., Computing in algebraic extensions, Computing, Supplement 4, 173-187 (1982) · Zbl 0576.12001
[17] Noether, E., Ein algebraisches Kriterium für absolute Irreduzibilität, Math. Ann., 85, 26-33 (1922) · JFM 48.0081.03
[18] Ostrowski, A., Zur arithmetischen Theorie der algebraischen Grössen, Göttinger Nachriehten, 1919, 279-296 (1919) · JFM 47.0067.03
[19] Reif, J., Logarithmic depth circuits for algebraic functions, Proc. 24th IEEE Symp. Foundations Comp. Sci., 138-144 (1983)
[20] Schmidt, W. M., Equations over finite fields. An elementary approach, Springer Lec. Notes Math., 536 (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.