I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P.

Here is a partial list that I have already compiled. Most of these are fairly straight-forward, I would be interested in some which are a little more obscure. I've also omitted some of the more obvious ones (e.g. an oracle which produces a random prime, or the smallest prime, which divides $n$). In each case $n$ represents the integer to be factored, which is assumed to be a non-square composite, and $i,j$ are positive integers.

There are several related functions depending on what response is returned by the oracle (instead of just 1 or 0) or by swapping less than or below with greater than or above, etc. In general, I am only including one from each case:

Decision Problems on $i$

  • $f_1(i) = 1$ if $i$ is less than the smallest prime factor of $n$, and $0$ otherwise.
  • $f_2(i) = 1$ if $i$ is greater than the largest prime factor of $n$, and $0$ otherwise.

Function Problems on $i$

  • $g_1(i) = $ the sum of the number of factors below $i$.
  • $g_2(i) = 1$ if the number of factors below $i$ is odd, $0$ otherwise.
  • $g_3(i) = $ the sum of the factors below $i$.
  • $g_4(i) = $ the sum of non-factors below $i$.
  • $g_5(i) = $ the distance from $i$ to the nearest factor of $n$.
  • $g_6(i) = (i!,n)$ the greatest common divisor between $i!$ and $n$
  • $g_7(i,j) = $ the power of i in $j!$

Function problems on $n$

  • $h_1(n) = $ the sum of the factors of n.
  • $h_2(n) = $ the ratio of $q/p$ where $p$ and $q$ are the innermost factors (closest above and below $\sqrt{n}$).
  • $h_3(n) = \phi(n)$ Euler's totient function
  • 3
    $\begingroup$ Can you define the problem "integer factorization" precisely? $\endgroup$ – usul Jun 14 '13 at 17:06
  • $\begingroup$ Given a non-prime square-free integer $n$ produce a list of all the prime factors of $n$. $\endgroup$ – Foo Barrigno Jun 15 '13 at 13:51

(This is shameless self-promotion.) If you don’t mind either assuming the generalized Riemann hypothesis (for $L$-functions of quadratic Dirichlet characters) or using randomized polynomial time, then the following search problems work:

  • Given integers $n,a$ such that the Jacobi symbol $\left(\frac an\right)=1$, output either a square root of $a$ modulo $n$, or a nontrivial factor of $n$.

  • Any PPA-complete problem, such as: given a circuit $C\colon\{0,1\}^m\to\{0,1\}^m$ computing an involution (i.e., $C(C(x))=x$ for every $x\in\{0,1\}^m$) such that $C(1^m)=1^m$, output an $x\ne1^m$ such that $C(x)=x$.

  • The weak pigeonhole principle: given a circuit $C\colon\{0,1\}^{2m}\to\{0,1\}^m$, output $x\ne y\in\{0,1\}^{2m}$ such that $C(x)=C(y)$.

  • $\begingroup$ WPP is not in random polynomial time? $\endgroup$ – 1.. Jan 17 '20 at 16:37
  • $\begingroup$ No, it is not (at least when relativized, or under plausible assumptions). $\endgroup$ – Emil Jeřábek Jan 17 '20 at 17:18

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.