A Scalable Hardware Circuit for Factoring an n-bit Integer: Analytic and Computational Perspectives

Abstract

This chapter addresses a prominent problem that is ubiquitous in scientific and engineering applications including the usually challenging task of cryptanalysis. This problem is the problem of integer factorization, i.e., the decomposition of a composite integer into a product of smaller integers, restricted herein to be prime integers. This is an intractable problem that might admit real-time hardware solutions for small bit sizes. This chapter suggests manual and automated scalable solutions for integer factorization based on equation solving over big Boolean algebras. The manual solution is illustrated over a form of 8-variable Karnaugh maps that is highly regular and modular. This solution covers the problem of 6 bits, which includes the problems of 5, 4, and 3 bits as special cases. Additionally, an automated solution is used, and the findings are then shown and briefly explained. These findings demonstrate the well-known evolution of temporal and spatial complexity with increasing input bit count. In future work, the largest possible hardware circuit that could be obtained via the automated solution is to be constructed, verified and tested. The complexity in our solution comes from two sources. One involves the task of finding the Boolean expressions for the solution. This task is slow, but it has to be done once, and only once, for a problem of a given size. The hardware implementation (e.g., an FPGA implementation) could serve as a ready real-time look-up solution not only of the pertinent problem but also of all smaller problems.