Viewing Single Post From: Using Crypto Books To Solve Knapsack Problem

Viewing Single Post From: Using Crypto Books To Solve Knapsack Problem
jdege	Jan 13 2008, 06:34 PM
Elite member Posts: 263 Group: Admin Member #246 Joined: December 7, 2006	Most of the crypto hobbiests I know are into books. They (we) tend to collect them, even - or especially - when we have no real use for them. David Kahn writes eloquently about his addiction: PREFACE TO A SALES CATALOGUE OF ANTIQUARIAN BOOKS ON CRYPTOGRAPHY. My own collection is far smaller, and on much less grand a scale. I've spent far less time and money on it. But I have managed to obtain copies of the books that as a child first interested my in crypto - John Peterson's How to Write Codes and Send Secret Messages, and Herbert S. Zim's Codes & Secret Writing. Many of you will be familiar with the Knapsack Problem. It's a mathematical puzzle with a crypto significance. The problem is given a set of items each with a certain size, how to select a subset of them such that the sum of the selected items is maximized, while not exceeding a specified value. If the number of items is large, a solution is far faster to verify than to find, which is why Merkle and Hellman suggested it as a possibility when the introduced the idea of Public Key Cryptography. In any case, I had a real-life problem, of this sort, and my solution involved some of my crypto books. I have a Mission-style cabinet in the living-room, we picked up used. It has three doors, two solid and one glass, but only one door pull - the other two were missing. I managed to find a replacement door pull that looked exactly the same as the originals, but the screw spacing was different. Now I don't know about you, but my cabinetry skills are such that I knew that trying to drill new holes on swinging doors would result in disaster. So I pulled the screws from one side of each hinge, and removed the doors. Installing the new hardware went off without a hitch. I also noticed a spot where the lamination had bubbled a bit, so I glued that down, clamped it up, and left things sit overnight. This morning, I took off the clamps, peeled back the plastic I had added to keep the glue from sticking where it wasn't supposed to, and the laminate looked good. So it was time to hang the doors. I've never found it easy to hold a door in place with one hand while working the screws and screwdriver with the other. It's a lot easier if the door is held up in the right position. These are internal hinges, so I was working with the doors fully open. What did I have, that would work? Books. They stack flat on the floor, and make a solid base. The only question is finding the right selection of books to result in the height I needed. That is, you guessed it, a knapsack problem. And it turns out that of the books I grabbed, the two that were critical to making up the right height were the two crypto paperbacks I mentioned above. Not because of their contents, but because they were only 1/4" and 3/8" thick. The cabinet doors are back on, the new hardware looks great. And I finally managed to use some of my crypto books in solving a real-life problem.
	When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

Using Crypto Books To Solve Knapsack Problem · General