My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
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 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?
CRGreathouse is offline  
 

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?
johnny is offline  
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.
CRGreathouse is offline  
January 24th, 2010, 04:28 AM   #4
 
Joined: Dec 2009
Posts: 7
Re: Identifying semiprimes

You could see some of the papers of Prof Ming-Deh Huang.
vin.san is offline  
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://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?
CRGreathouse is offline  
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 semi-primes, unfortunately, the only one
 
Reply

  My Computer Forum > Computer Science Forum > Algorithms

Tags
identifying, semiprimes



Thread Tools
Display Modes






Copyright © 2018 My Computer Forum Forum. All rights reserved.