# Complexity of generalizations of primality testing?

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:

1. 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.)

1. 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?)

• A problem intermediate between primality and factoring is deciding if an integer $N>1$ is squarefree, and I am pretty sure there is still no known way to efficiently decide whether or not $N$ is squarefree without factoring $N$. Note this is in contrast to 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. – KConrad Apr 11 '19 at 20:33
• (contd.) is their reliance on being able to say there exists a small number mod $m$ that lies outside a proper subgroup of the units mod $m$, such as being $O((\log m)^2)$ and Eric Bach showed you could take the $O$-constant to be 2 or 3 if you use GRH for Dirichlet $L$-functions. The way these tests (e.g., Miller-Rabin or Solovay-Strassen) differ is the proper subgroup of the units mod $m$ that occur in the justification of the polynomial running time of the test. So you could say that the "nonsingleton family of related problems" is the general problem of knowing proper subgroups of (contd) – KConrad Apr 11 '19 at 20:50
• the units mod $m$ are missing a small integer mod $m$. This kind of bound has lots of applications in number theory to problems not about primality testing, such as the running time of the Tonelli-Shanks algorithm (to solve $x^2 \equiv a \bmod p$ explicitly given that we know $(a|p) = 1$, say by quadratic reciprocity) or finding generators of the ideal class group of a number field $K$ having small norm (where small means compared to the size of $(\log |{\rm disc}(K)|)^2$). Look up Bach's paper (MR 1023756 on MathSciNet) and check later papers that rely on it. – KConrad Apr 11 '19 at 20:58
1) This is known to be polynomial time using a straightfoward reduction to "PRIMES": Compute the norm $$n$$ of the ideal under consideration. Next compute a minimal positive integer $$p$$ such that $$n$$ is a $$p$$-power. Now use "PRIMES IN P" to test if $$p$$ is prime. Next compute the prime decomposition of $$p\mathcal O_K$$ and determine the valuation of your ideal at the prime ideals lying above $$p$$. All the steps are polynomial time in the size of the input.