Design of a Hardware Circuit for Integer Factorization Using a Big Boolean Algebra

An Integer factorization is an intractable problem that might be handled in real time via hardware solution. Such a solution requires the extension of propositional logic to higher-order logics (e.g., first-order predicate logic) or the enlargement of two-valued Boolean algebra to a ‘big’ Boolean algebra. The paper derives a hardware circuit that factorizes a 6-bit integer X into two integers Y and Z of sizes 5 bits and 3 bits, respectively. The paper employs Boolean-equation solving techniques employing relatively large (8-variables and 6-variables) Karnaugh maps. The underlying Boolean algebra has 6 generators, 26 = 64 atoms, and 264 ≈ 1.8 1019 elements. The solution obtained for the 6-bits problem is easily and readily reduced to obtain or reproduce solutions for the problem in which X has 5 bits, 4 bits, and 3 bits, respectively. The feasibility of the proposed techniques is demonstrated and methods to study the scaling, complexity and automation issues are suggested. An automated version of the method is expected to compete well with the best solver available which currently handles up to 12 bits for the integer X to be factored.