Creating hard instances of computational problems can be easy (e.g., Factoring), cumbersome (e.g, SAT) or hard (e.g. Graph Isomorphism). So using a problem that allows to create instances in an easy way and then transform it into an instance of another problem is often a good idea, as long as the transformation is feasible. In this post i want to show how factoring can be reduced to a boolean formula $\varphi$ such that finding a satisfying assignment of $\varphi$ reveals a factor of the original integer. So if you think you found an algorithm that solves SAT in polynomial time, you should use this approach to convert a 2048-bit RSA instance to a SAT instance and test how it behaves :)
The approach is analogous to the approach of
ToughSAT. For a high level overview, the algorithm works like this:
Input: $N = pq$, with unknown primes $p$ and $q$.
- $n \leftarrow$ bitlength(N)
- Take $2n$ variables for the binary representation of $p$ and $q$ and write:
\begin{align*}
x_{n-1}x_{n-2}...x_1x_0 \cdot y_{n-1}y_{n-2}...y_1y_0
\end{align*} Then apply the school method for multiplying two integers.
- This multiplication creates a list of equations that heavily depend on each other.
- Replace each equation with an equivalent formula that only uses the boolean operators "and" and "or".
- Transform the boolean formula to a 3CNF
I will present the algorithm by an example:
