Factoring Integers by Solving Boolean Equations

How hard is it to factor rational integers?

We do not answer this question. But we do gain some insight into this question by reducing the task of factoring rational integers to that of solving Boolean equations.

Based on this approach, we show how to create a factoring algorithm, called Boolean factoring. Although this algorithm is not competitive with, for example, the quadratic sieve factoring algorithm, it leads to a number of new approaches to and a better understanding of the hardness of factoring.

Surprisingly, the Boolean equations arising from factoring have a highly algebraic structure. We show how to construct a ring G, which we call the ring of generic integers, in which these Boolean equations become a type of integer, i.e., generic integer. This ring has some unusual properties, one of which is that it is universal over the ring Z of rational integers. Based on the structure of this newly constructed ring, we devise an algorithm that in some cases computes the Hamming weight of a divisor of a rational integer n without actually factoring n. More results will be discussed.