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
Oracles which put integer factorization in P
ds.algorithms;reference request;oracles;factoring