Yes, there exist explicit fields for which polynomial factorization (specifically irreducibility testing) has exponential time complexity, either in terms of known upper bounds or conditional lower bounds. One notable example is the field of real algebraic numbers, denoted as ( \overline{\mathbb{Q}}_{\mathbb{R}} ), which consists of all real roots of polynomials with integer coefficients.

...

Yes. If you allow “explicit” to mean “effectively presented with decidable equality” (but without requiring the field operations to be efficient), then you can make the irreducibility problem as hard as you like, up to any decidable complexity class. In particular you can get EXPTIME-hardness (hence, under P ≠ EXPTIME, no polynomial-time algorithm), and you also recover the classical undecidabilit...

Below is a brief survey of what is known (and not known) about univariate factorization over “explicit” fields. By an explicit field we simply mean a field whose equality‐and‐basic‐operations are computable in some (reasonable) model.

1. “Classical’’ fields with polynomial‐time factoring
   – Q and number fields.
   Lenstra–Lenstra–Lovász (1982) give a deterministic polynomial‐tim...

Exponential-Time Factorization of Polynomials

This is an excellent question about the complexity landscape of polynomial factorization. You've correctly identified a gap in the literature between polynomial-time algorithms and undecidability results.

Current State of Knowledge

Most results on polynomial factorization fall into two categories:

1. Polynomial-time algorithms for:
   • Fi...

As far as we know to-day there is no “intermediate’’ example.
For every explicit (i.e. computable) field that has been investigated the situation is one of the following two:

1. Factorisation / irreducibility of univariate, densely represented polynomials is decidable in deterministic (or at worst Las-Vegas–randomised) time polynomial in the size of the input. Examples: ℚ (Lenstra...

An excellent and insightful question. You've correctly identified a gap in the landscape of computational problems between polynomial-time and undecidable, and polynomial factorization provides a perfect example of a problem that can occupy that middle ground.

Yes, there are explicit fields where polynomial factorization is known to require exponential time. We can construct such fields in at lea...

This is an excellent question about the complexity of polynomial factorization over various fields. Let me provide a comprehensive answer covering what is known about this problem.

Current State of Knowledge

Fields with Polynomial-Time Algorithms

As you mentioned, polynomial factorization is efficiently solvable over many common fields:

• Rational numbers (ℚ): The LLL algorithm provi...

First, note that the question is about explicit fields, meaning fields for which equality is decidable....

Yes – by building the field in a way that encodes an exponentially-hard decision problem one can obtain an “explicit’’ field for which even the irreducibility of quadratic polynomials is exponentially hard. The construction is completely effective, equality of field elements is decidable, and the hardness is unconditional (it follows from the deterministic time–hierarchy theorem).

For definite...