| To the best of my knowledge, if you're given a number that's a product of two primes, knowing that it is such doesn't make it any easier to factor.
Pollard's rho algorithm is the usual probablistic algorithm for factoring that you'll find in textbooks. It tends to be reasonably efficient given randomly chosen integers to factor, but the case of products of two large primes is pathologically hard. There is no known way to factor such numbers in probabilistic polynomial time, though neither is there any proof that none exists.
There is, however, an extremely efficient probablistic algorithm for testing primality: Miller-Rabin. There is also AKS which is a deterministic polynomial-time primality test, but it's O(n12) for an n-bit number, which means it's basically useless in practice. |
