Given a positive integer $n$ and $x \in (\mathbb{Z}/n\mathbb{Z})^*$ what is the most efficient way to find primes $q_1,q_2$ st $$q_1q_2 \equiv x \bmod n$$ when $n$ is large?
One option is just to take $q_1=2$ and then find the least prime $q_2 \equiv x/2 \bmod n.$ The bound on the least prime of this form is Linnik's theorem. Going by wikipedia (http://en.wikipedia.org/wiki/Linnik%27s_theorem) the best current result is $O(n^{5.2})$ which means that $O(n^{4.2})$ primality tests would be needed to find $q_2$ in the worst case. Can this be improved on?
If $n$ is not unreasonably large, I'd take advantage of the birthday paradox. You should only need to collect about $O(\sqrt{n})$ distinct residues of primes before you find two that multiply to $x$. This does require $O(\sqrt{n})$ memory unlike your Linnik's solution which is essentially constant memory.
Since you wouldn't be targeting any particular residue class, adding one more residue to your collection is not much slower than just finding the next prime (it only takes $O(\log n)$ time to decide if that residue is already in your collection, and since the collection is not very big you wouldn't have to discard many values on average).