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.

The $3$-bit multiplier from Figure $2$ extends easily to a $n$-bit multiplier in a straight forward way, in particular an $n$-bit multiplier can be arranged as a planar embedding in the plane (i.e. no lines are crossing each other). There is nothing against it to view this as a planar graph that contains $n^2$ subgraphs. To make the whole graph planar one has to care only about the planarity of the adder gadgets. So lets take a closer look at those subgraphs.

In the abstract sense, you can view the adder gadget as a subgraph with $8$ boundary nodes and an unknown number of inner nodes. There are $2^8 = 256$ possible combinations that these boundary nodes get input from $\{0,1\}^*$ or, when viewed as a graph, are used or not used in a perfect matching. For an adder gadget, the $8$ boundary nodes are divided into $4$ input and $4$ output nodes. One input combination forces one particular output combination. So from the total $256$ combinations only $16$ remain valid. This $16$ combinations are listed below in the function table of the adder gadget. The first column is just a counter. The next four columns represent the input nodes and cover all $16$ combinations . The last four columns show the output values. 

\begin{array}{c||c|c|c|c|c|c|c|c|c}
\hline
\text{no.} & p_j & r_\text{in} & q_i & c_\text{in} & \Rightarrow & p_j & r = q_jp_i+r+c \pmod{2} & c_\text{out} = \lfloor\frac{q_jp_i+r+c}{2} \rfloor & q_j \\
\hline
1 & 0 & 0 & 0 & 0 & \Rightarrow & 0 & 0 & 0 & 0 \\
2 & 0 & 0 & 0 & 1 & \Rightarrow & 0 & 1 & 0 & 0 \\
3 & 0 & 0 & 1 & 0 & \Rightarrow & 0 & 0 & 0 & 1 \\
4 & 0 & 0 & 1 & 1 & \Rightarrow & 0 & 1 & 0 & 1 \\
5 & 0 & 1 & 0 & 0 & \Rightarrow & 0 & 1 & 0 & 0 \\
6 & 0 & 1 & 0 & 1 & \Rightarrow & 0 & 0 & 1 & 0 \\
7 & 0 & 1 & 1 & 0 & \Rightarrow & 0 & 1 & 0 & 1 \\
8 & 0 & 1 & 1 & 1 & \Rightarrow & 0 & 0 & 1 & 1 \\
9 & 1 & 0 & 0 & 0 & \Rightarrow & 1 & 0 & 0 & 0 \\
10 & 1 & 0 & 0 & 1 & \Rightarrow & 1 & 1 & 0 & 0 \\
11 & 1 & 0 & 1 & 0 & \Rightarrow & 1 & 1 & 0 & 1 \\
12 & 1 & 0 & 1 & 1 & \Rightarrow & 1 & 0 & 1 & 1 \\
13 & 1 & 1 & 0 & 0 & \Rightarrow & 1 & 1 & 0 & 0 \\
14 & 1 & 1 & 0 & 1 & \Rightarrow & 1 & 0 & 1 & 0 \\
15 & 1 & 1 & 1 & 0 & \Rightarrow & 1 & 0 & 1 & 1 \\
16 & 1 & 1 & 1 & 1 & \Rightarrow & 1 & 1 & 1 & 1 \\
\hline
\end{array}
For example, line $7$ represents the case that the $i$-th bit of $p$ is zero and there is an input from the adder gadget from the same column but one row above, i.e., $r_{in} = 1$. The $c_{in}$ from the adder gadget diagonal above is the also $1$ and the $i$-th bit of $q$ is zero. The bits of $p$ and $q$ are simply relayed to the next adder gadget. $r$ and $c_{out}$ are calculated as shown in the header of the table. This is the usual way an adder gadget is defined in the literature.

In an $n$-bit multiplier one can show that the combinations $2$, $6$, $10$ and $14$ can not occur, although, they are actual valid adder gadgets combinations.

Figure 3 - The 16 combinations of valid input/output combinations for a adder gadget. A red arrow indicates a $1$ as input/output and no arrow indicates a zero.

Theorem 1. From the 16 possible combinations for the adder gadget, the input/output combinations $2$, $6$, $10$ and $14$ do not occur in an $n$-bit multiplier. 

Proof.  All four non occurring combinations have in common, that the $q_i$ is not used, meaning the $q_i$ input bit is $0$ and the $c_{in}$ input is used, meaning the $c_{in}$ bit is $1$. Since the $c_{in}$ bit is set, there must be a predecessor adder gadget, hence this adder gadget can not be in the first row of the $n$-bit multiplier. The $c_{in}$ bit is the output from the adder gadget one row above and one column to the right, which uses also the same $q_i$ bit (see Figure 2). So the adder gadget where the $c_{in}$ bit comes from must be in a state with $q_i = 0$ and $c_{out} = 1$.
However, there are only two combinations with this setting, namely, $6$ and $14$. That means, if a gadget in an $n$-bit multiplier is in state $2,6,10,14$ then the adder gadget diagonal above must be in state $6$ or $14$. Now for this predecessor gadget the same reasoning starts again. Its diagonal predecessor must be in the state $6$ or $14$. But since the $n$-bit multiplier has only finite many rows and, as explained above, the first row can not have gadgets in state $2,6,10,14$, the occurrence of an gadget in state $2,6,10,14$ at any position in the $n$-bit multiplier is impossible. Q.e.d.

Remark: Only adders in the state $1,3,9,11$ can be in the first row of the $n$-bit multiplier.

I implemented a $n$-bit multiplier and indeed this four states never occur in a multiplication. So we are left with $12$ combinations.

Theorem 2. Given an integer $n=pq$ that is the product of two $n$-bit prime numbers, then the graph $\mathcal{G}$ that represents a $n$-bit multiplier and is constructed out of a working adder gadget has exactly two perfect matchings that match with the two solutions $n=pq$ and $n=qp$.

To achieve the main goal, you can take two directions:

1) Try to find directly an planar graph for the adder gadget that has a perfect matching in the $12$ remaining cases and has no perfect matching in all other combinations. I you find one, congratulations, you can now factor integers in polynomial time. Just rebuild the $n$-bit multiplier with the adder gadget graph, assign edges to the output nodes, whenever the corresponding bit in the product is $1$ and run Edmonds/Blossom algorithm to find the matching.

2) Try to work with the permanent value of the subgraphs that represent the adder gadgets in order to work with the bipartite double cover of the graph, as shown in a previous blog post.

Option 1).  If you already started to search a graph for the adder gadget, i must disappoint you. If you look closer at the $12$ combinations one may observe that the cases $8$ and $11$ are problematic. They use an odd number of boundary nodes whereof all other cases use an even number. If you want to assure that a perfect matching exists in all $12$ cases, this difference in the parity of the used boundary nodes, prevents it. Just assume that the adder gadget has an even number of nodes in total. If you remove an odd number from the boundary nodes, you are left with an odd number of nodes. This odd number of remaining nodes must itself be able to build a perfect matching, which impossible. If the total number of nodes is odd, removing an even number causes the same problem.

Is there hope for Option 1? An option, which i spent some time on, is to measure how often each of the $12$ states occur during a multiplication. Can i reveal some non trivial information about the factorization even it the states $8$ and $12$ are broken?

I coded an $n$-bit multiplier and run it with two random $n$-bit prime numbers as the input. Then i logged for each of the $n^2$ adder gadget which state they take on during the multiplication. I converted this information into an image to get some first visual feedback about the distribution of the two states $8$ and $12$

Figure 4 - The multiplication of two random 256bit integers. The image is of size 256x256 pixels and each pixel represents an adder gadgets of the $256$bit multiplier. The number of occurrences for state 8 (red) and 11 (green) are 4249 and 4524. Note: We rectified the parallelogram shape of the $n$-bit multiplier for visual reasons.

Figure 5 - The multiplication of two 256bit integer, which  both have ~ 10% $1$ it is binary representation. The number of occurrences for state 8 (red) and 11 (green) are 408 and 652. Note: We rectified the parallelogram of the $n$-bit multiplier for visual reasons.

For the $n$-bit multiplier the number of possible input combinations is $2^{2n}$. The theoretical state space of the inner $n^2$ adder gadgets is $12^{n^2}$. In Figure 6 you can the three different pictures which show the multiplication of two $32$bit integers. The one on the left is just the multiplication of these input integer, in the middle i flipped one bit of one factor and on the right i flipped also a bit on the other factor.

Figure 6 - The distribution of state $8$ and $11$ and flipping $1$ and $2$ bit respectively.

So changing one bit of of 64 total bits does change several states of the involved adder gadgets.

So how could this help? Assume you find an adder gadget, that somehow "ignores" the states $8$ and $11$, then the hope is, that the perfect matching in the graph should still be unique and reveal information of the factorization in question.

In the moment i have no clue how this "ignore" could be realized. Another option to is to step over from perfect matchings to maximum matchings, which is also part of future work.

Option 2). This option is a little more complicated but has no direct obstacles. What you do have to find in this option is a graph $\mathcal{G}$ such that:

1. $\mathcal{G}$ must not be planar itself, but its bipartite double cover must be planar.
2. $\mathcal{G}$ has only edge weights $0$ or $1$
3. The permanent value of all minors of the adjacency matrix of $\mathcal{G}$ that correspond to a valid combination must be non zero and zero otherwise.

Option 2 is part of future work.