Design of a Digital Circuit for Integer Factorization via Solving the Inverse Problem of Logic

Abstract

In standard problems of digital circuit design, a switching function (two-valued Boolean function) is specified declaratively as a (usually incomplete) asserted relation R(X,Z), or equivalently as an equation R(X,Z) = 1, where X and Z are inputs and outputs, respectively. To obtain such a function constructively, one might use Boolean-function synthesis (which enlarges propositional logic to first-order predicate logic), or use a ‘big’ Boolean algebra (which acts as an enlargement of switching algebra). This paper explores the utility of Boolean-equation solving in handling the hard or intractable problem of integer factorization by constructing a hardware circuit that achieves this purpose in real time (at least for reasonably large bit sizes). The feasibility of the proposed scheme is verified via the manual solution of the smallest possible problem. However, the results obtained are really encouraging, as they can be automated in a straightforward fashion. A sequel forthcoming paper will treat the scaling, complexity, and automation issues, and will, in particular, determine the upper limit on the bit size that can be treated by the current technique.