# What is an efficient algorithm for prime decomposition? [closed]

I know of two methods for prime decomposition of a given integer:

• Method One: We find all prime factors by starting with the smallest prime number.

• Method two: We split the number as the product of two integers not necessarily primes and continue splitting each factor into further factors until all factors are primes.

My first question is how can I prove that any of these methods will give the correct prime decomposition? (no full solution is required as a hint is more than enough)

My second question is that what algorithm do computers use for decomposing a very large number into its prime factors?

## closed as off-topic by Saad, Mohammad Riazi-Kermani, TheSimpliFire, Namaste, Jyrki LahtonenMar 11 '18 at 13:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Saad, Mohammad Riazi-Kermani, TheSimpliFire, Namaste, Jyrki Lahtonen
If this question can be reworded to fit the rules in the help center, please edit the question.

• There are many many algorithms used for factoring, and none of them are particularly fast. A lot of computer security is based on the non existence of good factoring algorithms. – DanielV Mar 9 '18 at 12:28
• For the first question, first prove prime factorizations are unique, then prove that both algorithms produce a prime factorization. – DanielV Mar 9 '18 at 12:29
• @DanielV I think it's more appropriate to say that no good (as in, polynomial) factoring algorithms are known. If I'm not mistaken, proving that none can exist is equivalent to proving that $P \ne NP$. EDIT: Apparently it is suspected to be NP-intermediate, but not even that has been proven. – derpy Mar 9 '18 at 12:34
• As DanieIV said there are many algorithms available, you can choose whichever you like. For your first question you just write the code depending on your algorithm and check for the small values.As for how to judge the quality of algorithm its very subjective, it can depend on how fast it gives the answer or how much memory it took or simple whether it is complex or not – NewGuy Mar 9 '18 at 12:48
• A very nice software automatically and systematically factoring numbers, is yafu. – Peter Mar 9 '18 at 13:17

## 1 Answer

For very small numbers, trial division is the best. If the number is somewhat larger, the usual procedure is as follows :

• Trial division upto some limit, depending on the size of the number, $10^4$ to $10^6$ are typical treash-holds.

• Applying a fermat-pseudoprime-test

• Elliptic curve method (ECM) if the number is composite to find factors upto $20-40$ digits. More digits is also possible but usually time-consuming.

• Number field sieve (The best known general method upto about $120$ digits)

Sometimes, the pollard-rho-method or the p-1-method or the p+1-method finds non-trivial factors.

If the number has a special form, there might exist better methods and the trial division can be made with a larger treash-hold.