2

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 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).
How do I do it?

Community
  • 1
  • 1
Daniel
  • 30,896
  • 18
  • 85
  • 139
  • 1
    Oh, please let us know if you manage to do this. Because if you do then you have essentially broken all forms of public/private key encryption regardless of the exact algorithm. Goodbye ssl, goodbye ssh and more importantly goodbye encrypted military communications. – slebetman Dec 05 '10 at 14:18
  • 4
    Posts don’t die on Stack Overflow. The question is still there. So what’s the problem? – Konrad Rudolph Dec 05 '10 at 14:18
  • Are you sure you need to factor a large number? If you can choose the numbers, why not multiply lots of small primes until you get a number in your range? Then, you already know the factors... – jtdubs Dec 05 '10 at 14:18
  • Exact duplicate of [Factor a large number efficiently with gmp](http://stackoverflow.com/questions/4301434/factor-a-large-number-efficiently-with-gmp) – Konrad Rudolph Dec 05 '10 at 14:20
  • Please define "efficiently". People are telling you there is no way to do this efficiently, but unless you give some desired time constraints we can't tell you whether or not it can be done. – Jason S Dec 05 '10 at 14:22
  • 1
    Those of you who are telling the OP that this is impossible are not reading the question. It is a random number, not a number of the type used in cryptography (where those numbers are a product of 2 large primes). A random number has a 50% chance of being a factor of 2, a 33% chance of being a factor of 3, a 20% chance of being a factor of 5, etc., and is much more likely to be factored quickly than a cryptographic product of 2 large primes. – Jason S Dec 05 '10 at 14:28
  • 2
    @Jason: You are misunderstanding how cryptographically large numbers are generated. The two large primes are generated by sampling large, randomly generated numbers and checking if they are prime. You may be able to quickly factor out the 2s, 3s and 5s, but it will still take a long time to find the larger prime factors, like 27644437. If we're talking 2048-bit numbers then it is reasonable to expect some large prime factors. – Cameron Skinner Dec 05 '10 at 14:33
  • 1
    @Cameron: OP has said nothing about the random numbers being cryptographic keys. If I understand the OP's post, it is to keep generating large random numbers until one is found that can be factored. If I were doing this, I would test for division with small primes, then test the remaining factors for probable primality, and if not prime then I'd run a number sieve for some max time T, and if I can't factor completely, then get the next random number and repeat. – Jason S Dec 05 '10 at 14:45
  • @Jason: Sigh. Yes, I know the OP is not talking about key generation. The OP is asking for an efficient method to find prime factors of large numbers. This, in general, has no known solution. Key generation is simply an example. – Cameron Skinner Dec 05 '10 at 14:48
  • @Jason: "What I need is a way to efficiently factor(find prime factors of a number) large numbers". Does the OP want to find *a* factor, *some* factors or *all* factors? A factor is easy. Some factors is harder, depending on how big "some" is. All factors is practically impossible (in general). If you just want to find a large number that can be factored then set the low bit to zero and you're done. – Cameron Skinner Dec 05 '10 at 14:49

7 Answers7

2

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

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • Please explain the downvote. It may not please anyone, but that is the answer. – Konrad Rudolph Dec 05 '10 at 14:21
  • -1: "efficient" is not meaningful in this context without quantitative specification from the OP, who may be fine with days or weeks runtime. – Jason S Dec 05 '10 at 14:24
  • You're also ignoring the OP's comment: "The numbers are practically random so there is little chance it will be hard to factor" – Jason S Dec 05 '10 at 14:25
  • @Jason: that’s not the way I’m reading the question (pretty certain the OP would have specified if he was aware of the hardness of the problem, to avoid confusion, in particular since “efficient” in computer science pretty much implies sub-exponential) – but fair enough. – Konrad Rudolph Dec 05 '10 at 14:26
  • @Jason: "efficient" is perfectly meaningful in this context. The word has a well-known meaning in computer science. It is not the same as "acceptable run-time", for example quicksort is efficient but may not have an acceptable run-time if your list contains 17 billion items. – Cameron Skinner Dec 05 '10 at 14:26
  • 1
    @Jason: "The numbers are practically random so there is little chance it will be hard to factor" is a little suspect. RSA key generation is done with practically random numbers (albeit with the low bit always set to 1). – Cameron Skinner Dec 05 '10 at 14:27
1

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

Good luck!

1

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.

0

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

Cameron Skinner
  • 51,692
  • 2
  • 65
  • 86
Itay Karo
  • 17,924
  • 4
  • 40
  • 58
  • You're ignoring the OP's comment:"The numbers are practically random so there is little chance it will be hard to factor" – Jason S Dec 05 '10 at 14:27
  • @Jason: "The numbers are practically random so there is little chance it will be hard to factor" is a little suspect. RSA key generation is done with practically random numbers (albeit with the low bit always set to 1). – Cameron Skinner Dec 05 '10 at 14:28
0

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.

Jason S
  • 184,598
  • 164
  • 608
  • 970
0

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.

Daniel
  • 2,331
  • 3
  • 26
  • 35
0

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.

Cameron Skinner
  • 51,692
  • 2
  • 65
  • 86
  • Why the downvotes (for this and similar answers)? You asked for an efficient method to factor large numbers. There is no such method. Just because you don't like the reality of the situation is no reason to downvote a correct answer. – Cameron Skinner Dec 05 '10 at 14:24
  • You're ignoring the OP's comment:"The numbers are practically random so there is little chance it will be hard to factor" – Jason S Dec 05 '10 at 14:26
  • @Jason: "The numbers are practically random so there is little chance it will be hard to factor" is a little suspect. RSA key generation is done with practically random numbers (albeit with the low bit always set to 1). – Cameron Skinner Dec 05 '10 at 14:29
  • @Cameron: No. You're misinterpreting. RSA key generation is done with practically random numbers to purposefully generate primes. Then the two primes are multiplied together to produce a very-hard-to-factor composite. – Jason S Dec 05 '10 at 14:31
  • @Jason: I believe you are misunderstanding RSA key generation; you clearly believe I misunderstand it. The point is that RSA tests large random numbers for primality, which is exactly equivalent to factorisation. It does this twice, then multiplies them to get a non-prime key. – Cameron Skinner Dec 05 '10 at 14:37
  • @Cameron: we agree on all except your statement: "The point is that RSA tests large random numbers for primality, which is exactly equivalent to factorisation". As you are probably aware, this is done using probabilistic methods, a completely different approach than factorization. – Jason S Dec 05 '10 at 14:43
  • @Jason: Er...no. It is probabilistic, but it is certainly also factorisation. It just stops as soon as it finds one factor. – Cameron Skinner Dec 05 '10 at 14:45
  • @Jason: Remember that the term "efficient" is very general. There are certainly cases where you can find small factors quickly, but in general there is no efficient method to find any factor for any large number. – Cameron Skinner Dec 05 '10 at 14:46
  • @Cameron: read up on probabilistic methods for primality testing such as Miller-Rabin. They do not actually find any factors, but rather they use number-theoretical techniques for showing that a number is definitely composite or probably prime. – Jason S Dec 05 '10 at 14:49
  • @Cameron: I have to step in here. Primality testing is in fact quite distinct from factorisation. Primality testing can be done efficiently at least sind AKS. However, this is luckily (for cryptography) entirely unrelated to factorization. – Konrad Rudolph Dec 05 '10 at 14:52
  • Hmm. OK. Maybe I don't know as much as I think :) – Cameron Skinner Dec 05 '10 at 14:52