<p>(This is shameless <a href="http://arxiv.org/abs/1207.5220">self-promotion</a>.) 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:</p>

<ul>
<li><p>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$.</p></li>
<li><p>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$.</p></li>
<li><p>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)$.</p></li>
</ul>

CC BY-SA 4.0
2020-01-17T16:37:50.340Z
WPP is not in random polynomial time?
Turbo
CC BY-SA 4.0
2020-01-17T17:18:19.423Z
No, it is not (at least when relativized, or under plausible assumptions).
Emil Jeřábek
CC BY-SA 3.0
2013-06-18T15:28:54.793Z
2013-06-18T15:28:54.793Z
Emil Jeřábek
<p>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.</p>

<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.</p>

<p>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:</p>

<h2>Decision Problems on $i$</h2>

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

<h2>Function Problems on $i$</h2>

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

<h2>Function problems on $n$</h2>

<ul>
<li>$h_1(n) = $ the sum of the factors of n.</li>
<li>$h_2(n) = $ the ratio of $q/p$ where $p$ and $q$ are the innermost factors (closest above and below $\sqrt{n}$).</li>
<li>$h_3(n) = \phi(n)$ Euler's totient function</li>
</ul>

CC BY-SA 3.0
2013-06-15T13:51:10.913Z
Given a non-prime square-free integer $n$ produce a list of all the prime factors of $n$.
Foo Barrigno
CC BY-SA 3.0
2013-06-14T17:06:33.110Z
Can you define the problem "integer factorization" precisely?
usul
<ds.algorithms><reference-request><oracles><factoring>
Oracles which put integer factorization in P
Foo Barrigno
# Oracles which put integer factorization in P

(Asked by: username_0 on 2013-06-14)

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

**Tags:** ds.algorithms, reference-request, oracles, factoring

> **Comments:**
> **username_1**: Can you define the problem "integer factorization" precisely?  
> **username_0**: Given a non-prime square-free integer $n$ produce a list of all the prime factors of $n$.  

---

## 1 answers

### Answer by username_2 on 2013-06-18. Score: 6

(This is shameless [self-promotion](http://arxiv.org/abs/1207.5220).) 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)$.

> **Comments:**
> **username_3**: WPP is not in random polynomial time?  
> **username_2**: No, it is not (at least when relativized, or under plausible assumptions).  

---

