ABSTRACT
Now that we are able to quickly recognize primes as primes, it remains to compute the prime factorization of (positive) integers. This is the tougher part of the story. Research efforts for decades have miserably failed to produce efficient algorithms for factoring integers. Even randomization does not seem to help here. Today’s best integer-factoring algorithms run in subexponential time which, although better than exponential time, makes the factoring problem practically intractable for input integers of size only thousand bits.
