Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field.
It is known that over some explicit fields, testing irreducibility of polynomials is undecidable [1]. Though, over many fields, the irreducible factorization of polynomials is known to be computable in polynomial time, either deterministically (over $\mathbb Q$ [2] or any number field) or probabilistically (over finite fields [3]). Here the size of the input is the size of the dense representation of the polynomial, that is the list of all its coefficients.
Is there an explicit field for which
- either the best known algorithm has an exponential running time,
- or (better) there exists an exponential lower bound for irreducibility testing?
Quick clarification: There may be very different explicit fields, depending on the complexity (for instance) on the equality test or of the standard operations (addition, multiplication). Actually, I am not aware of any result about polynomial factorization which is not a polynomial time upper bound, or undecidability. So I am interested in any kind of different result (exponential time is just an example). Conditional lower bounds are of interest too.
References.
[1] A. Fröhlich et J. C. Shepherdson (1955): On the factorisation of polynomials in a finite number of steps.
[2] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász (1982): Factoring polynomials with rational coefficients.
[3] E.R. Berlekamp (1967): Factoring Polynomials Over Finite Fields.