Identifying semiprimes

[CRGreathouse]

I'm often looking for good ways to work with numbers. One problem that sometimes comes up is factoring large numbers. Factoring out small primes (where 'small' is less than, say, ten million) is easy to do, but for larger numbers (say, 16 decimal digits) better factoring algorithms are needed. When numbers get to be more than perhaps a hundred bits (30 decimal digits) even factoring numbers becomes rather challenging.

Sometimes I have a problem where knowing that there are 'not many' prime factors suffices. Toward that end, I'd like an algorithm for testing whether a number has at most two prime factors. Of course I want a fast algorithm: If I could spend n^(1/2) steps I could just divide by all the numbers under the square root and be done. But when n is large its square root is also large, and grows too quickly to be useful. Likewise, if I test for factors under the cube root I can know that a number has at most two prime factors. But n^(1/3) steps is still much too large.

Of course I could just factor the number with any of a number of algorithms that are practical for small-ish numbers. These algorithms are sometimes O(n^(1/4)) and many are even subexponential -- o(n^e) for any e > 0. (Exponential here refers to exponential in the size of the number, log(n) rather than n itself.)

These methods, though, seem like 'too much' for the problem at hand since I don't need to extract the factors. Is there some good way to test this?

[johnny]

Currently, what programming languages do you use to identify factors of primes?

[CRGreathouse]

Doesn't matter, I'll take code in any language.

I'm nominally using C++, but it's really C as I don't think I'm using any of the C++ extensions. I'm trying to keep it fast; none of the virtual machine/intermediate language nonsense here.

[vin.san]

You could see some of the papers of Prof Ming-Deh Huang.

[CRGreathouse]

I didn't immediately see anything of interest in
http://www-rcf.usc.edu/~mdhuang/publications.html

There were several papers about factoring polynomials, but none about factoring integers as such, nor any about identifying/bounding number of factors without factoring. Any particular suggestions?