It seems that factoring a number known to be composite is in its own interesting little complexity class, e.g. polynomial time using quantum computing even though no one has proved $\mathsf{P} = \mathsf{NP}$ for quantum computing.

Are there interesting, non-obvious examples of problems with polynomial-time verifiability for solutions, which have been shown to be polynomial-time equivalent to factoring a composite number into primes, under the classical non-quantum computational model?

  • $\begingroup$ Since deciding whether a given natural is prime is in $\mathsf{P}$, how is it relevant that the input is "known to be composite"? $\endgroup$ – Raphael Sep 17 '13 at 8:14

I assume that you meant to consider the difference between $BQP$ and $NP$ rather than $P$ and $NP$. $P$ is primarily only defined using deterministic time bounded Turing Machines while $BQP$ is specific to bounded error polytime quantum computers.

Factoring is, of course, in $NP$ (function version being in $\mathcal{F}_{NP}$), so it should easily follow that anything polynomial time reducible to factoring is going to have a polynomial time verifier. If you were actually asking if any polynomial time verifiers share the same "hardness" as factoring, then the answer is: no idea. It would require making assumptions about whether or not factoring is in $P$.

I am afraid that I could not find a non-number theoretic set of problems that are known to be polynomial time reducible to factoring. Despite much study, the complexity of factoring is still very open. Knowing where it falls will provide many additional answers to your question. I'll go over what I have:

Two well known ones are computing Quadratic Residuosity and computing the Euler Totient, $\phi (n)$. The equivalence between factoring and Euler totient is very straight forward, especially to those that have ever looked into RSA.

A paper by Tibor Jager and Jorg Schwenk shows that the Quadratic Residuosity Problem and Subgroup Membership Problem are "generically equivalent" to factoring.

It is still open as to whether or not the Discrete Log Problem and the decision version of Composite Residuosity are also equivalent. Though, Pomykała wrote on the polynomial time reducibility of Discrete Log (composite moduli) to Factoring recently and presented a deterministic subexponential time algorithm for just that.

You may have a lot of success researching the Hidden Subgroup Problem. For finite Abelian groups, quantum computers have the advantage of being able to do this in polynomial time via Fourier transforms. Shor uses the fact that Factoring, Discrete Log, and some others are special cases of this problem.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.