3
$\begingroup$

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

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

  1. 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?
Improve this question
$\endgroup$
9
  • $\begingroup$ @YCor I intentionally capitalized PRIMES to refer to the computational problem of primality testing, as in the title of the AKS paper. Perhaps "primality testing" is better? $\endgroup$
    – Tim Campion ♦
    Apr 11, 2019 at 19:34
  • 2
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Apr 11, 2019 at 20:33
  • 2
    $\begingroup$ The surprise about AKS was that it did not rely 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.) An AMS Notices article 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. What is common to some other primality tests that would run in polynomial time if you grant GRH-type statements (contd). $\endgroup$
    – KConrad
    Apr 11, 2019 at 20:47
  • 1
    $\begingroup$ (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) $\endgroup$
    – KConrad
    Apr 11, 2019 at 20:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Apr 11, 2019 at 20:58

1 Answer 1

Reset to default
3
$\begingroup$

Sorry, I don't have enough reputation to comment.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.