"Trivial" factorization algorithms

[Fusion_power]

What is the least number of iterations required to fully factor a given number?

For example, I can fully factor the number 144 in 12 iterations. Though I can improve this by using a few exclusions of non-potential factors. (trial division would result in 5 iterations to test 144) This is NOT optimized for Mersenne numbers which can be speeded up by using 2kp+1 and +/-1 mod 8

Note that a single iteration is a sequence of operations such as sqrt, multiply, divide, etc that results in a given potential factor being evaluated.

Fusion

[trilliwig]

You might want to check out Factorizations of bⁿ±1, b=2,3,5,6,7,10,11,12 Up to High Powers available at http://www.ams.org/online_bks/conm22/ . The Introduction to the Main Tables (sections III through V) contains a lot of fascinating history of the Cunningham Project and the advancement of technology since it began in 1925.

Specifically you'd want sections III.B.2, IV.A.2, and V.A.2 if you want information on factorization algorithms. If you want information on primality proving algorithms (a distinctly different problem) you'd want sections III.B.3, IV.A.3, and V.A.3. A lot of forum regulars have their names up in lights there.

[trilliwig]

Shanks' SQUFOF (Square Form Factorization) method. This uses the theory of quadratic fields to find ambiguous forms with discriminant a small multiple of N, the number to be factored. This can lead to a splitting of N. It has the property that the numbers dealt with are generally no larger than 2 sqrt(N), so to factor numbers up to 62-bit size, it can use 32-bit math the majority of the time. This makes it very efficient for "hard" numbers in that size range. However, it is still an exponential time algorithm, taking O(sqrt(p)) operations to find a factor p of N, or O(N^(1/4)).

http://www.mersenneforum.org/showthread.php?t=2960

Shanks also came up with another factorization method using class groups, bearing the name Shanks' Class Group method, funnily enough. It also uses O(N^(1/4)) operations to factor N, but may be O(N^(1/5)) if the Generalized Riemann Hypothesis is true.

Yet another class group method is SPAR, independently discovered by Schnorr and Lenstra, and by Atkin and Rickert. SPAR = Shanks, Pollard, Atkin and Rickert. The latter two implemented it and have used it to factor a few Cunningham numbers. This method uses a subexponential number of operations (better than exponential, worse than polynomial) but also uses very little storage, similar to ECM and p-1.