Factoring as a decision problem 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?
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:

D:  given n and k, does n have a divisor d satisfying 1 &lt; d &lt;= k?
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.