Rastavljanje na faktore

Prirodan broj se rastavlja na faktore tako što se deli sa najmanjim prostim brojem kojim je on deljiv. Postupak se nastavlja dok je to moguće. Na primer, broj 360 se rastavlja na faktore na sledeći način:

1. 360=2*180
2. 360=2*2*90
3. 360=2*2*2*45
4. 360=2*2*2*3*15
5. 360=2*2*2*3*3*5
6. 360=2*2*2*3*3*5*1

Literatura

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective. Springer. ISBN 0-387-94777-9.  Chapter 5: Exponential Factoring Algorithms, pp. 191-226. Chapter 6: Subexponential Factoring Algorithms, pp. 227-284. Section 7.4: Elliptic curve method, pp. 301-313.
• Donald Knuth (1997). „Seminumerical Algorithms, Section 4.5.4: Factoring into Primes”. The Art of Computer Programming. 2 (3. изд.). Addison-Wesley. стр. 379—417. ISBN 0-201-89684-2. 

Spoljašnje veze

• A collection of links to factoring programs
• Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp. 3-22. download
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781-793 (2004). August 2005 version PDF
• Source code by Paolo Ardoino, Three known algorithms and C source code.
• Factorization Source Code: by Paul Herman & Ami Fischman, C++ source code for many factorization algorithms including Pollard Rho & Shor's.