Stategy for prime factorization How do I prime factorize big numbers, such as 8435674686325652 without having to make millions of divisions?
 A: 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.
A: 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.   
