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

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?

• Check this out: en.wikipedia.org/wiki/General_number_field_sieve Sep 29, 2019 at 22:09
• It will in general be a "difficult" problem to factor arbitrary numbers. It is thanks to that difficulty that rsa encryption is difficult to break. Sep 29, 2019 at 22:12
• For all we know, though, factorization might still be in P (even if P!=NP). Sep 29, 2019 at 22:35
• For a method that is more efficient than trial division, but not so hard to understand, try the Pollard rho algorithm. I think this is a good place to start looking into more advanced factorization methods.
– MJD
Sep 30, 2019 at 5:28

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.