There is a known polynomial-time algorithm for testing whether an integer is prime. I'm wondering what is known about problems in this neighborhood:

**Questions:**

- What happens over other number fields? Say $K$ is a number field, and suppose I have an explicit basis for $\mathcal O_K$ over $\mathbb Z$. Given $a_1, \dots, a_n \in \mathcal O_K$ expressed in this basis, is there a polynomial-time algorithm to decide if the ideal $(a_1, \dots, a_n) \subseteq \mathcal O_K$ is prime? How about if $n=1$, i.e. it's a principal ideal? Conversely, do there exist number fields (explicitly described as above) for which primality testing is not in $P$?

(I suspect what's known may depend on $K$ as well as various number-theoretic conjectures.)

- Somewhat surprisingly to me, having a polynomial-time primality has not led to a polynomial-time factoring algorithm. Are there any "intermediate" problems between primality testing and factoring which admit efficient algorithms? For example, given $n \in \mathbb Z$, is there an efficient way to put a lower bound on the smallest prime factor of $n$? Or to estimate the sum of the factors of $n$, or something like that?

(Again, I suspect what's known may depend on various conjectures?)

**EDIT:** (in response to KConrad's insightful comments:)

- If the ideas of the AKS algorithm don't easily adapt to such generalizations, then are there at least
*some*other problems which the ideas of the AKS algorithm can be used to solve?

contrastto the case of polynomials (in characteristic 0): we know how to decide if $f(x)$ in $\mathbf Q[x]$ is squarefree easily: check that $(f(x),f'(x)) = 1$ (it is necessary and sufficient). In $\mathbf Z$ there is no analogue of differentiation that leads to anything resembling that test for being squarefree in the case of integers. $\endgroup$notrely on deep ideas. (The initial version of the test did include technical estimates in analytic number theory, but pretty quickly others were able to streamline the prerequisites so the test only needs elementary estimates.) AnAMS Noticesarticle about the AKS test was called "PRIMES Is in P: A Breakthrough for 'Everyman'," which reflects the surprise at its accessibility in terms of the math needed to explain the test. Whatiscommon to some other primality tests that would run in polynomial time if you grant GRH-type statements (contd). $\endgroup$4more comments