c++ - Factor a large number efficiently with gmp

Question

I need to get all the prime factors of large numbers that can easily get to 1k bits. The numbers are practically random so it shouldn't be hard. How do I do it efficiently? I use C++ with GMP library.

EDIT: I guess you all misunderstood me.
What I mean by prime a number is to get all prime factors of the number.
Sorry for my english, in my language prime and factor are the same :)

---

clarification (from OP's other post):

What I need is a way to efficiently factor(find prime factors of a number) large numbers(may get to 2048 bits) using C++ and GMP(Gnu Multiple Precession lib) or less preferably any other way. The numbers are practically random so there is little chance it will be hard to factor, and even if the number is hard to factor, I can re-roll the number(can't choose though).

Answer 1

A good start would be some pre-filtering with small primes, say about all primes lower than 100 000 or so. Simply try to divide by every single one of them (create a table which you then load at runtime or have it as static data in your code). It might seem slow and stupid, but if the number is totally random, this will give you some factors very fast with a huge probability. Then look at the remaining number and decide what to do next. If it is quite small (what "small" means is up to you) you could try a primality test (there is something in GMP i think) and if it gives it is a prime, you can in most of the cases trust it. Otherwise you have to factor it further.

If your numbers are really huge and you care about performance, then you definitely need to implement something more sophisticated than just a stupid division. Look at Quadratic Sieve (try wikipedia). It is quite simple but very powerful. If you are up to the chalenge, try MPQS, a variant of the quadratic sieve algorithm. This forum is a good source of information. There are even existing implementations of a tool you need - see for example this.

Note though that numbers with 1k bits are huge by all means. Factoring such a number (even with MPQS or others) might take years if you are lucky and forever if not. I think that MPQS performs well with numbers of about 100-400 bits (if they are composed of two primes almost equally large, which is the hardest case of course).