How do I prime factorize big numbers, such as 8435674686325652 without having to make millions of divisions?
Asked
Active
Viewed 117 times
2
-
1http://www.wolframalpha.com/input/?i=factorize+8435674686325652 – njguliyev Sep 02 '13 at 07:34
-
3@user1067083: No, factoring is not known to be NP-complete. – Robert Israel Sep 02 '13 at 07:39
2 Answers
3
There's an extensive article here about some methods to factor integers.
In general, something like trial divisions and Fermat factorization should be used to reduce the number by weeding out small factors. For example, the number you gave is divisible by $2$.
Next, something more advanced like Pollard's rho algorithm can be used to pick out moderate sized factors.
If the number doesn't work with any of those, something heavy-duty like a quadratic sieve or the general number field sieve is appropriate.
3
Finding the prime decomposition of integers is known to be a very hard problem. The number you give as an example is not that large, so it can easily be factorized using any reasonable factorization algorithm, but it will perform millions of divisions. Truly large numbers, such as those that are the product of two prime numbers each having several hundred digits, are simply too hard even for the best algorithms. This fact is used as the basis for the safety of the RSA algorithm. See here for more info.
Ittay Weiss
- 79,840
- 7
- 141
- 236
-
They might perform millions of operations, but not necessarily divisions. In fact I suspect that most reasonable factoring algorithms would perform rather few divisions. – Robert Israel Sep 02 '13 at 07:49
-
That is an interesting comment @RobertIsrael. I would suspect most algorithms will not directly use division on the given number they factorize, but that they still use plenty of divisions. But I'm not really well-versed in state-of-the-art factoring algorithms. – Ittay Weiss Sep 02 '13 at 08:48