| The Boolean Factoring Algorithm was introduced by Lomonaco in 2013. This is an algorithm for reduction of the integer factorization problem to DNF-SAT. While DNF-SAT is in P, the reduction itself takes exponential time. This thesis expands on the variant called Multiplicative Boolean Factoring proposed in the same paper. Various optimizations are introduced and proofs for some of the results are presented. A rigorous running time analysis of the algorithms is provided. An implementation of the two algorithms was carried out in the Java programming language. Our thesis details this implementation and experimental running time analysis performed using the same. The largest number factored by our implementation so far is the 50-bit integer 1,090,093,705,635,337 in 37.67 seconds. The possibility of a sub-exponential time reduction to DNF-SAT and an extension to the discrete logarithm problem are posited as avenues for future work. |
