zbMATH — the first resource for mathematics

Factoring multivariate polynomials over finite fields. (English) Zbl 0577.12013
The author presents an algorithm for the factorization of multivariate polynomials with coefficients in a finite field which is polynomial-time in the degrees of the polynomial to be factored. This algorithm makes use of a new basis reduction algorithm for lattices over \({\mathbb{F}}_ q[Y].\)
In the case of two variables the algorithm is similar to the polynomial- time algorithm for the factorization of polynomials in one variable with rational coefficients [the author, H. W. Lenstra jun. and L. Lovász, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001] and to that given by A. L. Chistov and D. Yu. Grigor’ev [Prepr. LOMI E-5- 82 (1982; Zbl 0509.68029)]. If \(f\in {\mathbb{F}}_ q[X_ 1,X_ 2,...,X_ t]\) for \(t>2\) the problem is reduced to the case \(t=2\) by substituting high enough powers of \(X_ 2\) for \(X_ 3\) up to \(X_ t\).

11T06 Polynomials over finite fields
68W30 Symbolic computation and algebraic computation
12D05 Polynomials in real and complex fields: factorization
65Yxx Computer aspects of numerical algorithms
Full Text: DOI
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] Berlekamp, E.R., Factoring polynomials over large finite fields, Math. comp., 24, 713-735, (1970) · Zbl 0247.12014
[3] Brown, W.S., The subresultant PRS algorithm, ACM trans. math. software, 4, 237-249, (1978) · Zbl 0385.68044
[4] Chistov, A.L.; Grigoryev, D.Yu., Polynomial-time factoring of multivariable polynomials over a global field, (1982), Lomi preprints E-5-82, Leningrad · Zbl 0509.68029
[5] Edmonds, J., Systems of distinct representatives and linear algebra, J. res. nat. bur. standards, 71B, 241-245, (1967) · Zbl 0178.03002
[6] \scE. Edmonds and J. von zur Gathen, A polynomial-time factorization algorithm for multivariate polynomials over finite fields, in “Proceedings 10th international colloquium on automata, languages and programming,” LNCS 154, 250-263.
[7] Lenstra, A.K.; Lenstra, H.W.; Lovåsz, L., Factoring polynomials with rational coefficients, Math. ann., 261, 515-534, (1982) · Zbl 0488.12001
[8] Mahler, K., An analogue to Minkowski’s geometry of numbers in a field of series, Ann. of math., 42, 488-522, (1941) · JFM 67.0140.01
[9] Yun, D.Y.Y., The hensel lemma in algebraic manipulation, (1974), MIT Cambridge, Mass, Garland, New York, 1980
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.