ABSTRACT
Factoring is the problem that calls for a positive integer as input, and requires as output a multiset of prime numbers whose product equals the input. From a theoretical point of view, that is why polynomial time algorithms are preferred to exponential time algorithms. In practice, polynomial time algorithms are usually faster than exponential time algorithms on real cases. The matrices below it show what would be the resulting successive iterations of Gaussian elimination. Standard algorithms for solving nonlinear and systems of linear equations are also efficient, but require more careful analysis of the time required to achieve adequate precision. As rules of thumb, usually n can be taken to be a natural measure of size such as the number of variables, polynomial time algorithms are fast in practice, and non-polynomial time algorithms are slow in practice. Consider more carefully the time required to find the maximum of n numbers. The natural parameter to use is n.
