Chapter 8 Number Theory216
receiver does using the Pulverizer —but it is not known how to factornintop
andqin any reasonable amount of time whennis very large. Maybe with a little
more studying of number theory, you will be the first to figure out how to do it.
Although, we should warn you that Gauss worked on it for years without a lot to
show for his efforts. And if you do figure it out, you might wind up meeting some
serious-looking fellows who work for a Federal agency....
8.9 What has SAT got to do with it?
So why does the world, or at least the world’s secret codes, fall apart if there is an
efficient test for satisfiability? To explain this, remember that RSA can be man-
aged computationally because multiplication of two primes is fast, but factoring a
product of two primes seems to be overwhelmingly demanding.
Now designing digital multiplication circuits is completely routine. This means
we can easily build a digital circuit out ofAND,OR, andNOTgates that can take two
input stringsu;vof lengthn, and a third input string,z, of length2n, and “check”
ifzrepresents the product of the numbers represented byuandv. That is, it gives
output 1 ifzrepresents the product ofuandv, and gives output 0 otherwise.
Now here’s how to factor any number with a length2nrepresentation using a
SAT solver. Fix thezinput to be the representation of the number to be factored.
Set the first digit of theuinput to 1, and do a SAT test to see if there is a satisfying
assignment of values for the remaining bits ofuandv. That is, see if the remaining
bits ofuandvcan be filled in to cause the circuit to give output 1. If there is such
an assignment, fix the first bit ofuto 1, otherwise fix the first bit ofuto be 0. Now
do the same thing to fix the second bit ofuand then third, proceeding in this way
through all the bits ofuand then ofv. The result is that after2nSAT tests, we
have found an assignment of values foruandvthat makes the circuit give output
- Souandvrepresent factors of the number represented byz. This means that if
SAT could be done in time bounded by a degreedpolynomial inn, then2ndigit
numbers can be factored in time bounded by a polynomial innof degreedC 1. In
sum, if SAT was easy, then so is factoring, and so RSA would be easy to break.
Problems for Section 8.1
Practice Problems
Problem 8.1.
Prove that a linear combination of linear combinations of integersa 0 ;:::;anis a
linear combination ofa 0 ;:::;an.
