Oracles which put integer factorization in P

Question

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

Answer 1

(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)$.