Factoring Polynomials over Algebraic Number Fields
Author:
- Susan LandauSLSusan Landau
- 1 February 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (1) , 184-195
Abstract
We show that if $f(x)$ is a polynomial in $Z [ \alpha ][ x ]$, where $\alpha $ satisfies a monic irreducible polynomial over Z, then $f(x)$ can be factored over $Q(\alpha )[ x ]$ in polynomial time. We also show that the splitting field of $f(x)$ can be determined in time polynomial in ([Splitting field of $f(x): Q $], $\log | (x) |$).
Keywords
This publication has 22 references indexed in Scilit:
- A polynomial-time reduction from bivariate to univariate integral polynomial factorization1982
- Irreducible polynomials with integral coefficients have succinct certificatesJournal of Algorithms, 1981
- The Subresultant PRS AlgorithmACM Transactions on Mathematical Software, 1978
- Number Fields1977
- An inequality about factors of polynomialsMathematics of Computation, 1974
- The Calculation of Multivariate Polynomial ResultantsJournal of the ACM, 1971
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- On Euclid's Algorithm and the Theory of SubresultantsJournal of the ACM, 1971
- Factoring polynomials over large finite fieldsMathematics of Computation, 1970
- Systems of distinct representatives and linear algebraJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967