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$ Sep 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$
    – JMoravitz
    Sep 29, 2019 at 22:12
  • 1
    $\begingroup$ For all we know, though, factorization might still be in P (even if P!=NP). $\endgroup$
    – user7530
    Sep 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$
    – MJD
    Sep 30, 2019 at 5:28

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .