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?
1$\begingroup$ Check this out: en.wikipedia.org/wiki/General_number_field_sieve $\endgroup$– IntegrateThisSep 29, 2019 at 22:09
3$\begingroup$ 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. $\endgroup$– JMoravitzSep 29, 2019 at 22:12
1$\begingroup$ For all we know, though, factorization might still be in P (even if P!=NP). $\endgroup$– user7530Sep 29, 2019 at 22:35
1$\begingroup$ 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. $\endgroup$– MJDSep 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.