Derivation of a Scalable Solution for the Problem of Factoring an n-bit Integer

Abstract

The problem of integer factorization is ubiquitous in scientific and engineering applications including the challenging task of cryptanalysis. This problem is intractable but might admit real-time hardware solutions for small bit sizes. This paper 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. Moreover, the automated solution is implemented, and subsequently its results are presented and discussed briefly. These results show the notorious evolution of the temporal and spatial complexities as the number of input bits increases. Based on the automated solution, the largest possible hardware circuit obtained via the automated solution is to be constructed, verified and tested. Such a hardware implementation (e.g., FPGA implementation) could serve as a ready real-time look-up solution not only of the pertinent problem but also of all smaller problems.