Derivation of a Scalable Solution for the Problem of Factoring an n-bit Integer
Ali Muhammad Rushdi *
Department of Electrical and Computer Engineering, King Abdulaziz University, P. O. Box 80204, Jeddah 21589, Saudi Arabia.
Sultan Sameer Zagzoog
Department of Electrical and Computer Engineering, King Abdulaziz University, P. O. Box 80204, Jeddah 21589, Saudi Arabia.
Ahmed Said Balamesh
Department of Electrical and Computer Engineering, King Abdulaziz University, P. O. Box 80204, Jeddah 21589, Saudi Arabia.
*Author to whom correspondence should be addressed.
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.
Keywords: Manual and automated scalable solutions, integer factorization, Boolean-equation solving, modular Karnaugh map, algorithmic implementation