Chapter 8 Number Theory282
Let’s begin with the observation from Section 3.2 that a digital circuit can be
described by a bunch of propositional formulas of about the same total size as the
circuit. So testing circuits for satisfiability is equivalent to the SAT problem for
propositional formulas (see Problem 3.18).
Now designing digital multiplication circuits is completely routine. We can eas-
ily build a digital “product checker” circuit out ofAND,OR, andNOTgates with 1
output wire and4ndigital input wires. The firstninputs are for the binary repre-
sentation of an integeri, the nextninputs for the binary representation of an integer
j, and the remaining2ninputs for the binary representation of an integerk. The
output of the circuit is 1 iffijDkandi;j > 1. A straightforward design for such
a product checker uses proportional ton^2 gates.
Now here’s how to factor any numbermwith a length2nbinary representation
using a SAT solver. First, fix the last2ndigital inputs—the ones for the binary
representation ofk—so thatkequalsm.
Next, set the first of thendigital inputs for the representation ofito be 1. Do a
SAT test to see if there is a satisfying assignment of values for the remaining2n 1
inputs used for theiandjrepresentations. That is, see if the remaining inputs for
iandjcan be filled in to cause the circuit to give output 1. If there is such an
assignment, fix the firsti-input to be 1, otherwise fix it to be 0. So now we have set
the firsti-input equal to the first digit of the binary representations of anisuch that
ijDm.
Now do the same thing to fix the second of thendigital inputs for the represen-
tation ofi, and then third, proceeding in this way through all theninputs for the
numberi. At this point, we have the completen-bit binary representation of an
i > 1suchijDmfor somej > 1. In other words, we have found an integeri
that is a factor ofm. We can now findjby dividingmbyi.
So afternSAT tests, we have factoredm. This means that if SAT for digital
circuits with4ninputs and aboutn^2 gates could be determined by a procedure
taking a number of steps bounded above by a degreedpolynomial inn, then2n
digit numbers can be factored inntimes this many steps, that is, with a number of
steps bounded by a polynomial of degreedC 1 inn. So if SAT could be solved in
polynomial time, then so could factoring, and consequently RSA would be “easy”
to break.
8.13 References
[2], [41]
