Probabilistic algorithm for determining bit multipliers in the problem of factoring Integers
Yuri Ogorodnikov · 2015
The paper presents a probabilistic algorithm for determining the bit multipliers in the problem of factoring integers, the most famous application of which is the use of the algorithm RSA. An algorithm is based on the reduction of factorization problem to the problem of satisfiability of Boolean formulas, that is, in turn, reduce to continuous real functional. The obtained functional is minimized by method of simple iterations and the results are projected from real variables to Boolean with using Bayesian approach. The numerical experiments were performed and the variants of further application are proposed. An important advantage of the developed method is the polynomial time of calculating.