Factorization of Multivariate Polynomials Over Finite Fields
- 1 July 1985
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 45 (171) , 251-261
- https://doi.org/10.2307/2008063
Abstract
We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. A deterministic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field.Keywords
This publication has 13 references indexed in Scilit:
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial FactorizationSIAM Journal on Computing, 1985
- Parallel Algorithms for Algebraic ProblemsSIAM Journal on Computing, 1984
- Hensel and Newton Methods in Valuation RingsMathematics of Computation, 1984
- Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomialsIEEE Transactions on Information Theory, 1983
- On the complexity of multiplication in finite fieldsTheoretical Computer Science, 1983
- A polynomial-time reduction from bivariate to univariate integral polynomial factorizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A New Algorithm for Factoring Polynomials Over Finite FieldsMathematics of Computation, 1981
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970
- Factoring Polynomials Over Finite FieldsBell System Technical Journal, 1967