Factoring as Optimization

The factoring of biprimes is proposed as a framework for exploring unconstrained optimization algorithms. A mapping from a given factoring problem to a positive degree four polynomial F is described. F has the properties that the global minima, which specify the factors, are at F = 0, and that all coefficients can be chosen to be of order unity. The factoring of biprimes is an attractive test bed because a large number of different F functions can be generated easily, in such a way that the complexity of the resulting minimization problem can be easily controlled. Representing the problem in this form also gives interesting perspectives on why factoring is hard. This framework suggests new approaches for optimization algorithms aimed at solving combinatorically hard problems. In this paper a new unconstrained optimization algorithm, ‘curvature inversion descent’ (CID), is described. It has the property that local minima can often be deterministically escaped. CID is illustrated with an 8-dimensional minimization problem generated by factoring a small biprime. For that problem, gradient descent with restarts finds the solution 31% of the time; with CID, this increases to 88% of the time.