Here is a break-down graph of operations done in 4-bit integer multiplication.

91 Views Asked by At

2

The blue nodes represent the number $b = b_3b_2b_1b_0$, and the green nodes represent the number $a = a_3a_2a_1a_0$. The yellow nodes are the output bits after multiplying $a \cdot b$. If $a\cdot b$ would not normally fit in a 4-bit word, then the nodes only represent the lower bits of that multiplication. Would working with this graph make integer factorization easier?

For example. Here's the graph supposing that all $c_i$ bits are $1$. And we've moved up to 5-bit multiplication: enter image description here

The other red nodes are immediately deduced to be $1$. Now what's the minimal set of remaining nodes such that if we knew their bit settings, then we can immediately deduce the rest of the graph?

1

There are 1 best solutions below

0
On BEST ANSWER

You can be absolutely certain that everybody who works in factorization knows how multiplication works, and how to wire up a straightforward binary multiplier. In spite of this, factorization is still considered a hard problem -- which ought to answer your question about whether drawing such a network makes factorization easier.

Essentially what you're proposing is to rephrase the factorization problem as a boolean-circuit SAT problem, but SAT is generally believed to be even harder than integer factorization (in the sense that SAT is NP-complete whereas factorization probably isn't). So that wouldn't generally be expected to represent progress.