| Actually, I can prove that knowing that a number is a product of two primes doesn't help you factor it any more quickly than by a multiple of two:
Suppose you have a factoring algorithm A which guarantees correct output only if the input is a product of two primes. Then you can simply run this algorithm in parallel with a general-case factoring algorithm B, alternating between running A and B at periodic intervals. If A terminates earlier than B, then check to see if its output is correct; this is a simple matter of multiplying the factor back together and seeing if you get the original input. If A gave incorrect output, then just continue running B. Then in the worst case, B terminates immediately after A terminates with an incorrect result, in which case you could have saved half of your effort by not running A. |
