## 07 June 2008

### Interactive proofs

After a series of ego-enhancing posts it's time to get back to something better. I've read on the bus a popular paper by László Lovász. It must be shared.

Why read this. You could go ahead an read the paper I link to. Or you could continue reading this. This post contains the same ideas, is shorter, and is targeted to a (good) working programmer.

Factoring. Can you factor the integer 15? It's 3\times5. OK, that was easy. But I bet you'll find it harder to factor 2458520708919619073142040881007027206573813634042770527212029117113260478602067483 even if I tell you that it has exactly two prime factors. No one knows how to factor numbers efficiently. Yet, if I tell you that one factor is 6348726349827463298746322987643379 you can probably quickly verify that this factor is prime and figure out the other prime factor (by division). You can now even come up with a similar problem yourself, after you observe that primes are dense.

Electronic envelope. Lovász considers a scenario involving two people playing chess, Alice and Bob. It gets late and they must interrupt the game when Alice is about to announce her move. She doesn't want Bob to think about his move all night. So she wants to tell Bob her move now but put it in an envelope that Bob will be able to open only in the morning when she gives him the key. The solution is simple: Encode the move as a four digit number, find a big prime that begins with those digits, multiply it by an even bigger prime, and tell Bob the answer. Then Bob, in principle, could factor the number and look at the first four digits of the smaller prime. Fortunately, that's too much work for one night.

Hamiltonian cycle. Finding a Hamiltonian cycle in a graph is another hard problem, and we'll use it to illustrate even more magic.