<p>Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in user2917198's <a href="https://cstheory.stackexchange.com/questions/25466/factoring-as-a-decision-problem#comment63373_25466">comment</a>).</p>

<p>Here is the reference:
J. Watrous. An introduction to quantum information and quantum circuits. ACM SIGACT News 42(2): 52–67, 2011. 
<a href="https://cs.uwaterloo.ca/~watrous/Papers/IntroductionQuantumCircuits.pdf" rel="nofollow noreferrer">https://cs.uwaterloo.ca/~watrous/Papers/IntroductionQuantumCircuits.pdf</a></p>

<p>As pointed out in the Introduction of the paper, the issues are not specific to Factoring/BQP, but more in general, «they concerns basic manipulations of quantum circuits».</p>

<p>If you just wanted to see how to cast the factoring problem in a decision problem, refer to Jeffrey Shallit's answer.</p>

CC BY-SA 3.0
2014-08-07T14:24:33.090Z
2014-08-07T14:24:33.090Z
2017-04-13T12:32:28.053Z
Alessandro Cosentino
<p>In fact, given natural numbers $x$ and $N$, deciding whether $x$ is a square modulo $N$ or not is a typical decision problem. If you can solve this problem efficiently, then you can factor $N$ efficiently, too. </p>

CC BY-SA 3.0
2014-11-05T16:03:32.607Z
No. This is the quadratic residuosity problem, which is assumed intractable, but not known to be as hard as factoring. You are confusing it with the problem of computing square roots modulo $N$, which is equivalent to factoring up to randomized polynomial-time reductions, but is not a decision problem.
Emil Jeřábek
CC BY-SA 3.0
2014-11-05T15:15:59.510Z
2014-11-05T16:02:28.673Z
2014-11-05T16:02:28.673Z
Pigmann
<p>If I understand correctly, factoring can be encoded as SAT decision problem and then recover the actual solution. For unknown $x,y$ and given $N$, encode to SAT the problem $ x \cdot y = N, x &gt; 1 , y &gt; 1$. Basically all you need is an adder circuit and few gates. Call the resulting formula $\phi$. If $\phi$ is satisfiable, then $N$ is composite. Set the first bit of $x$ to $1$ and check if $\phi'$ is satisfiable. If it is, you guessed correctly and try with the second bit. Otherwise set it to $0$ and continue with the second bit. This is linear in the numbers of bits.</p>

<p>(Actually in practice real SAT solvers will give you the complete
solution if it exists).</p>

CC BY-SA 3.0
2014-08-07T11:22:32.860Z
2014-08-07T11:22:32.860Z
joro
<p>Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time.   There are a number of ways to do this.  To name just two:</p>
<ol>
<li>D:  given n and k, does n have a divisor d satisfying 1 &lt; d &lt;= k?</li>
<li>D:  given n and j, is the j'th bit of the smallest nonunit divisor of n equal to 1?</li>
</ol>
<p>If you can solve 1, then you can identify d using binary search.  Once you have d, you can then continue with n/d until the complete factorization is achieved.  2 is similar.</p>

CC BY-SA 4.0
2014-08-07T11:23:58.523Z
2021-03-25T19:04:01.677Z
2021-03-25T19:04:01.677Z
Jeffrey Shallit
<p>I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision problem? And is there a paper which shows that Shor's algorithm implies this decision problem is in BQP?</p>

CC BY-SA 3.0
2014-08-07T12:32:32.897Z
As Jeffrey Shality said, it is indeed in BQP. I just want to point you to some online discussions: http://rjlipton.wordpress.com/2011/01/23/is-factoring-really-in-bqp-really/
http://rjlipton.wordpress.com/2011/01/25/factoring-is-in-bqp/
user2917198
CC BY-SA 3.0
2014-08-07T14:41:51.050Z
This seems to be all addressed on wikipedia (http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity). How to turn factoring into a decision problem is definitely not research level. I am not sure the quantum part is either, but Lipton did need a clarification, so I guess that's fine.
Sasho Nikolov
<cc.complexity-theory><ds.algorithms><complexity-classes><quantum-computing><quantum-information>
Factoring as a decision problem
Sam Burville
# Factoring as a decision problem

(Asked by: username_0 on 2014-08-07)

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision problem? And is there a paper which shows that Shor's algorithm implies this decision problem is in BQP?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, quantum-computing, quantum-information

> **Comments:**
> **username_1**: As Jeffrey Shality said, it is indeed in BQP. I just want to point you to some online discussions: http://rjlipton.wordpress.com/2011/01/23/is-factoring-really-in-bqp-really/ http://rjlipton.wordpress.com/2011/01/25/factoring-is-in-bqp/  
> **username_2**: This seems to be all addressed on wikipedia (http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity). How to turn factoring into a decision problem is definitely not research level. I am not sure the quantum part is either, but Lipton did need a clarification, so I guess that's fine.  

---

## 4 answers

### Answer by username_7 on 2014-08-07. Score: 24 | Accepted answer

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time. There are a number of ways to do this. To name just two:

1. D: given n and k, does n have a divisor d satisfying 1 < d <= k?
2. D: given n and j, is the j'th bit of the smallest nonunit divisor of n equal to 1?

If you can solve 1, then you can identify d using binary search. Once you have d, you can then continue with n/d until the complete factorization is achieved. 2 is similar.


---

### Answer by username_3 on 2014-08-07. Score: 9

Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in username_1's [comment](https://cstheory.stackexchange.com/questions/25466/factoring-as-a-decision-problem#comment63373_25466)).

Here is the reference:
J. Watrous. An introduction to quantum information and quantum circuits. ACM SIGACT News 42(2): 52–67, 2011.
<https://cs.uwaterloo.ca/~watrous/Papers/IntroductionQuantumCircuits.pdf>

As pointed out in the Introduction of the paper, the issues are not specific to Factoring/BQP, but more in general, «they concerns basic manipulations of quantum circuits».

If you just wanted to see how to cast the factoring problem in a decision problem, refer to username_7's answer.


---

### Answer by username_4 on 2014-11-05. Score: -1

In fact, given natural numbers $x$ and $N$, deciding whether $x$ is a square modulo $N$ or not is a typical decision problem. If you can solve this problem efficiently, then you can factor $N$ efficiently, too.

> **Comments:**
> **username_5**: No. This is the quadratic residuosity problem, which is assumed intractable, but not known to be as hard as factoring. You are confusing it with the problem of computing square roots modulo $N$, which is equivalent to factoring up to randomized polynomial-time reductions, but is not a decision problem.  

---

### Answer by username_6 on 2014-08-07. Score: -4

If I understand correctly, factoring can be encoded as SAT decision problem and then recover the actual solution. For unknown $x,y$ and given $N$, encode to SAT the problem $ x \cdot y = N, x > 1 , y > 1$. Basically all you need is an adder circuit and few gates. Call the resulting formula $\phi$. If $\phi$ is satisfiable, then $N$ is composite. Set the first bit of $x$ to $1$ and check if $\phi'$ is satisfiable. If it is, you guessed correctly and try with the second bit. Otherwise set it to $0$ and continue with the second bit. This is linear in the numbers of bits.

(Actually in practice real SAT solvers will give you the complete
solution if it exists).


---

