
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
December 29th, 2007, 08:45 PM  #1 
Joined: Dec 2007 Posts: 232  Identifying semiprimes
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 smallish 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? 
My Computer Forum is free to register and we welcome everyone! 
December 30th, 2007, 12:13 AM  #2 
Joined: Dec 2007 Posts: 187  Re: Identifying semiprimes
Currently, what programming languages do you use to identify factors of primes?

December 30th, 2007, 01:28 PM  #3 
Joined: Dec 2007 Posts: 232  Re: Identifying semiprimes
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. 
January 24th, 2010, 04:28 AM  #4 
Joined: Dec 2009 Posts: 7  Re: Identifying semiprimes
You could see some of the papers of Prof MingDeh Huang.

March 2nd, 2010, 06:12 PM  #5 
Joined: Dec 2007 Posts: 232  Re: Identifying semiprimes
I didn't immediately see anything of interest in http://wwwrcf.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? 
November 23rd, 2011, 05:46 AM  #6 
Guest Joined: Posts: n/a  Re: Identifying semiprimes
to what to call the numbers or our techniques of identifying them? .... love to have a list of semiprimes, unfortunately, the only one
