Skip to content
Research Article Open access CC BY 4.0

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/45009

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.

Manual and automated scalable solutions integer factorization Boolean-equation solving modular Karnaugh map algorithmic implementation

References (31)

  1. 1 Boolean Methods in Operations Research and Related Areas [DOI]
  2. 2 Boolean Functions: Theory, Algorithms, and Applications
  3. 3 Boolean functions and equations
  4. 4 Boolean Reasoning: The Logic of Boolean Equations
  5. 5 Factoring Large Numbers with the TWIRL Device [DOI]
  6. 6 Lattice Functions and Equations [DOI]
  7. 7 Using variable-entered Karnaugh maps to produce compact parametric general solutions of Boolean equations [DOI]
  8. 8 K-means Clustering for Multispectral Images Using Floating-Point Divide [DOI]
  9. 9 A Boolean minimization procedure using the variable-entered Karnaugh map and the generalized consensus concept [DOI]
  10. 10 Scalable Hardware for Sparse Systems of Linear Equations, with Applications to Integer Factorization [DOI]
  11. 11 Skolem functions for factored formulas [DOI]
  12. 12 Further Improved Variable-Entered Karnaugh Map Procedures for Obtaining the Irredundant Forms of an Incompletely-Specified Switching Function [DOI]
  13. 13 Integer factorization with a neuromorphic sieve [DOI]
  14. 14 On Reliability Evaluation by Network Decomposition [DOI]
  15. 15 A New Cryptographic Scheme Utilizing the Difficulty of Big Boolean Satisfiability [DOI]
  16. 16 A Novel Method for Compact Listing of All Particular Solutions of a System of Boolean Equations [DOI]
  17. 17 An efficient method for integer factorization [DOI]
  18. 18 Factoring Integers With a Brain-Inspired Computer [DOI]
  19. 19 CAIRN3: An FPGA Implementation of the Sieving Step with the Lattice Sieving
  20. 20 Digital Circuit Design Utilizing Equation Solving over ‘Big’ Boolean Algebras [DOI]
  21. 21 Derivation of All Particular Solutions of a ‘Big’ Boolean Equation with Applications in Digital Design [DOI]
  22. 22 Formal Derivation of a Particular Input of a Single AND (OR) Gate in Terms of Its Output and Other Inputs [DOI]
  23. 23 Satisfiability in Big Boolean Algebras via Boolean-Equation Solving [DOI]
  24. 24 A Dedicated Sieving Hardware [DOI]
  25. 25 Yet Another Sieving Device [DOI]
  26. 26 Factoring large numbers with programmable hardware [DOI]
  27. 27 Solution of a class of Boolean equations [DOI]
  28. 28 Efficient solution of systems of Boolean equations [DOI]
  29. 29 Design of a Digital Circuit for Integer Factorization via Solving the Inverse Problem of Logic [DOI]
  30. 30 The Vertex-Frame Method for Obtaining Minimal Proposition-Letter Formulas [DOI]
  31. 31 Handbook of applied cryptography [DOI]

Cited by 6

Utilization of the Karnaugh Map in Exploring Cause-effect Relations Modeled by Partially-defined Boolean Functions

A. Rushdi, Raid Mohammad Salih Badawi · Journal of Engineering Research and Reports · 2021

Utilization of Symmetric Switching Functions in the Symbolic Reliability Analysis of Multi-State k-out-of-n Systems

A. Rushdi · International journal of mathematical, engineering and management sciences · 2019

Reliability Analysis of a Commodity-Supply Multi-State System Using the Map Method

A. Rushdi, Abdulghani Bakur Alsayegh · Journal of Advances in Mathematics and Computer Science · 2019

Switching-Algebraic Analysis of Multi-State System Reliability

A. Rushdi, Mohamed A. Al-Amoudi · Journal of Engineering Research and Reports · 2019

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.