Factoring via perfect matchings in an n-bit multiplier graph

Factoring integers is a well studied topic in mathematics and computer science. The number of approaches to this problem numerous. There are even some graph related approaches to this problem. One particular, but not very efficient way, which i also covered in a previous blog post, is to convert an integer to a 3-USAT formula and find the unique satisfying assignment. I never heard of an approach that converts the integer factorization problem to a perfect matching problem.

Main Goal. What we want to accomplish with our approach is to build a planar graph $\mathcal{G}$ that reassembles an $n$-bit multiplier. $\mathcal{G}$ should be build in a way that it has exactly one perfect matching (or some derived graph has a perfect matching) and this perfect matching reveals the factorization of the given product $pq$.

One way to realize multiplication of two $n$-bit numbers $p$ and $q$ in hardware is to build a network of cascading $n^2$ adder gadgets. Such a construction is called an $n$-bit multiplier and has $2\times n$ input nodes that are assigned with the $2\times n$ bits of the two input numbers $p$ and $q$. Consequently, it also has $2\times n$ output nodes that represent the $2\times n$ bits of the final product $pq$. Each of the involved $n^2$ adder gadgets has $4$ input and $4$ output nodes and is illustrated in Figure 1.

Figure 1 - An adder gadget with 4 input and 4 output nodes. Two nodes with the same color represent a pair of input and output nodes, i.e., the green $p_i$ in the input area gets the input of the $i$-bit of the input integer $p$ and the green node in the output area simply outputs the same bit  and hands it over to the next adder gadget.

The meaning of the different colors in the figure are:

1. GREEN $p_i$: The $i$-th bit of the input integer $p$
2. RED $r$: The result output of an previous adder gadget
3. YELLOW $q_i$: The $i$-th bit of the input integer $q$
4. WHITE $c_{in}$: The carry output of an previous adder gadget.

An $n$-bit multiplier is an arrangement of the these $n^2$ adder gadget as shown in Figure 2 for the case $n=3$.

Figure 2 - $3$-bit multiplier with $9$ adder gadgets.

Matchings are perfect

💦 One of my favorite object in graph theory are Matchings, especially Perfect Matchings (PMs). Let me restate the definition of a PM briefly:

Definition (Perfect Matching). Given a graph $\mathcal{G} = (E,V)$, then a Perfect Matching $M$ is a set of pair-wise non-adjacent edges from $E$, such that every vertex in $V$ is touched by one edge in $M$.

Here is a little example for a two PMs in a graph:

Figure 1 - Top: The original graph $\mathcal{G}$; Below: The red lines indicate two example perfect matchings in $\mathcal{G}$

This post list some of the properties of PMs regarding finding and counting them in different graphs types. During writing this posts, i found that a similar listing can also be red in [6].