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

