Factoring large numbers [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

Factor a large number efficiently with gmp

I know I already posted it, but people misunderstood what I meant, and until I fixed it the post died.

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 Multipl开发者_开发百科e 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).

How do I do it?

---

There is no efficient way (probably). This assumption is the basis of modern cryptography.

---

http://en.wikipedia.org/wiki/General_number_field_sieve

Good luck!

---

Why do you think it will not be hard to factor? Yes, there will be some small factors. But the rest will be large enough in a number of that size that it will often take some serious work to factor.

I would suggest trial divisions by some small primes to get the small fish out of the pond. Then you might try Pollard's rho method, but I doubt it has a chance on numbers with that many bits. Better would be a quadratic sieve.

---

Have you tried the quadratic sieve or the general number field sieve? (QS simpler and easier to implement, GNFS faster for very large numbers, but your numbers may not be large enough for GNFS to be much faster than QS)

edit: According to a paper by Eric Landquist, the crossover point between QS and GNFS is about 110 digits = approx 365 bits.

---

If i am not missing anything This is known to be a "difficult" problem. http://en.wikipedia.org/wiki/Integer_factorization. i.e. it is currently impossible.

---

There is no known way to efficiently factor large numbers. See Wikipedia for a discussion of why and the state of the art.

As the comments have pointed out, the difficulty of this problem is the basis of much modern cryptography, particularly public-key encryption.

What you could do is store a table of small primes and work through that table dividing your large number by each candidate prime as it goes. If the number is "too hard" (i.e. you run out of small primes) then re-roll.

---

A way of doing this efficiently will break many the currently in use encryption algorithms.
This is an NPC problem, so....