More efficient and sure ways to finding prime factorization of any integer != 0,1

Question

By fundamental theorem of arithmetic every integer has a prime decomposition, but I don't know how to find them. Is there a general strategy for finding a prime decomposition of a number. The number I was working on is 4,849,845. Is there a better way than to just keep decomposing it? Or decompose it in a perhaps more efficient manner?

Answer 1

Usually, when a number $N$ has to be factored, the following strategy is used :

$(1)$ Trial division upto, lets say, $10^6$ to find very small factors. If $N$ has a special form, we can apply trial division to larger limits (for example, if we have a Mersenne-number)

$(2)$ If $N$ has no small factor, apply a primality test. If $N$ is prime, we are done.

$(3)$ Find small factors with the pollard-rho-method or the p-1-method.

$(4)$ Find intermediate factors (about $20-40$ digits) with ECM (elliptic curve method)

$(5)$ If $N$ is small enough and still not factored, apply the number field sieve (siqs or mpqs)

Numbers upto about $60$ digits can be factored , for example with pari/gp , quite fast.

A faster and more efficient program is yafu, but it might be a problem to run it on windows 10-systems.

I do not know why, but I had problems when I tried this on a computer in our chess club.

If you want to check a large number for primality, the best known program is PFGW.