Derivation of a Scalable Solution for the Problem of Factoring an n-bit Integer
Ali Muhammad Rushdi, Sultan Sameer Zagzoog, Ahmed Said Balamesh
Journal of Advances in Mathematics and Computer Science · pp. 1–22 · Published 24 Dec 2018
10.9734/JAMCS/2019/45009Abstract
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.
References (31)
- 1 Boolean Methods in Operations Research and Related Areas [DOI]
- 2 Boolean Functions: Theory, Algorithms, and Applications
- 3 Boolean functions and equations
- 4 Boolean Reasoning: The Logic of Boolean Equations
- 5 Factoring Large Numbers with the TWIRL Device [DOI]
- 6 Lattice Functions and Equations [DOI]
- 7 Using variable-entered Karnaugh maps to produce compact parametric general solutions of Boolean equations [DOI]
- 8 K-means Clustering for Multispectral Images Using Floating-Point Divide [DOI]
- 9 A Boolean minimization procedure using the variable-entered Karnaugh map and the generalized consensus concept [DOI]
- 10 Scalable Hardware for Sparse Systems of Linear Equations, with Applications to Integer Factorization [DOI]
- 11 Skolem functions for factored formulas [DOI]
- 12 Further Improved Variable-Entered Karnaugh Map Procedures for Obtaining the Irredundant Forms of an Incompletely-Specified Switching Function [DOI]
- 13 Integer factorization with a neuromorphic sieve [DOI]
- 14 On Reliability Evaluation by Network Decomposition [DOI]
- 15 A New Cryptographic Scheme Utilizing the Difficulty of Big Boolean Satisfiability [DOI]
- 16 A Novel Method for Compact Listing of All Particular Solutions of a System of Boolean Equations [DOI]
- 17 An efficient method for integer factorization [DOI]
- 18 Factoring Integers With a Brain-Inspired Computer [DOI]
- 19 CAIRN3: An FPGA Implementation of the Sieving Step with the Lattice Sieving
- 20 Digital Circuit Design Utilizing Equation Solving over ‘Big’ Boolean Algebras [DOI]
- 21 Derivation of All Particular Solutions of a ‘Big’ Boolean Equation with Applications in Digital Design [DOI]
- 22 Formal Derivation of a Particular Input of a Single AND (OR) Gate in Terms of Its Output and Other Inputs [DOI]
- 23 Satisfiability in Big Boolean Algebras via Boolean-Equation Solving [DOI]
- 24 A Dedicated Sieving Hardware [DOI]
- 25 Yet Another Sieving Device [DOI]
- 26 Factoring large numbers with programmable hardware [DOI]
- 27 Solution of a class of Boolean equations [DOI]
- 28 Efficient solution of systems of Boolean equations [DOI]
- 29 Design of a Digital Circuit for Integer Factorization via Solving the Inverse Problem of Logic [DOI]
- 30 The Vertex-Frame Method for Obtaining Minimal Proposition-Letter Formulas [DOI]
- 31 Handbook of applied cryptography [DOI]
Cited by 6
A. Rushdi, Raid Mohammad Salih Badawi · Journal of Engineering Research and Reports · 2021
A. Rushdi, Raid Mohammad Salih Badawi · 2021
A. Rushdi, O. M. Alsalami · 2020
A. Rushdi · International journal of mathematical, engineering and management sciences · 2019
A. Rushdi, Abdulghani Bakur Alsayegh · Journal of Advances in Mathematics and Computer Science · 2019
A. Rushdi, Mohamed A. Al-Amoudi · Journal of Engineering Research and Reports · 2019
Related research
- Design of a Hardware Circuit for Integer Factorization Using a Big Boolean Algebra — shares topic coverage
- Design of a Digital Circuit for Integer Factorization via Solving the Inverse Problem of Logic — shares topic coverage
- Connections on Valuated Binary Tree and Their Applications in Factoring Odd Integers — shares topic coverage
- More Connections on Valuated Binary Tree and Their Applications in Factoring Odd Integers — shares topic coverage
- Complexity of Finding Values of the Generalized Taxicab Number — shares topic coverage
Article metrics
Real usage data collected on this platform.
47
Page views
0
PDF downloads
12
Outbound clicks
6
Citations
Views over time
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
Traffic sources
Referring site, by host.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.