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:
- 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?