Combining Fixed-point Iteration Method and Bayesian Rounding for Approximation of Integer Factorization Problem

Abstract

We consider the special case of the 3-SAT problem stemming from the well known integer factorization problem, which is widely used in various cryptography algorithms. For every instance of our 3-SAT setting, it is known that the given 3-CNF is satisfiable by a unique truth assignment, and the goal is to find this assignment (which is called a solution of the problem). Since the complexity status of the factorization problem is still undefined, development of approximation algorithms and heuristics adopts interest of numerous researchers. One of promising approaches to construction of approximation techniques is based on real-valued relaxation of the given 3-CNF followed by minimizing of the appropriate differentiable loss function, and subsequent rounding of the fractional minimizer obtained. Actually, algorithms developed this way differ by the rounding scheme applied on their final stage. We propose a new rounding scheme based on Bayesian learning. Numerical evaluation shows that this scheme outperforms algorithms using the classic rounding up to 37.5%.