Friday, July 26, 2013

Miss Liberty 5: Outnumbering #2

            Miss Liberty and I were standing at the bottom of a small amphitheater. A little way up the slope was a control panel, and standing before it was a black sphere six feet in diameter.
            Miss Liberty pointed out a slogan written on the side of the control panel: ON COMPANY BUSINESS. We nodded grimly at each other; for that could mean only one thing. It meant that we were in the clutches of the Celestial Intervention Agency; the deadliest, trickiest, and most bureaucratic spy agency in the Universe!
            With a loud WHIRR the black sphere turned on its vertical axis, revealing an opening; it was really a large round chair. A man sat inside. He was dressed in a sober business suit; he was rather corpulent; he wore sideburns and a mustache, though the top of his head was bald.
            “Who are you?” asked Liberty.
            He said, “I am #2.”
            Liberty asked, “Who is #1?”
            #2 said scornfully, “You are #0.”
            “I am not a number,” said Liberty. “I am a Free Spirit!”
            “You are here for information,” said #2. “I shall provide you with that information, then hand you over to my agents for final disposal. State three questions.”
            “Well, I was wondering about this map,” said Miss Liberty, taking a badly-worn chart out of her robe. “Look: it’s all divided up into countries. I don’t see why, by the way; people are much the same anywhere you go.”
            “And what about this map?” #2 asked warily.
            “It needs some colors,” she complained. “As you can see, it’s all in black and white. A line sketch; how drab! It would be so nice to color these areas in.”
            “Obviously, no two neighboring countries should be the same color,” #2 said, “or we couldn’t tell the boundary.”
            “And there’d be no point to a boundary,” Liberty added. “So what I was wondering is this; how many colors suffice to color this map?”
            “Four colors suffice for all planar maps,” #2 said bluntly.
            “You’re sure,” Liberty said.
            “Quite sure. My operatives have proven it,” said #2. He pushed a button on the control console; a panel opened on the side facing us; and an immensely thick computer printout slid out. It fell with a loud THUD at our feet.
            “That computer printout is a formal proof of the Four Color Map Theorem,” said #2. “Examine it at your leisure.”
            Miss Liberty and I looked at each other; then we shrugged our shoulders. Maybe that was a proof. I suppose it was, if their theoretical analysis was right, their computer was sound, and its programs were correct. I don’t know; what do you think?
            “Ask your next question,” said #2.
            “You people like to be efficient; so I’m sure you can help me with this next problem,” said Miss Liberty. “You see, I want to work out a minimum-distance tour.”
            “So you’re going on a tour, are you?” #2 asked Miss Liberty. He appeared interested in this information.
            Miss Liberty said, “You see, one of these years, sooner than you expect, I’m going to take a tour of the 365 largest cities on Planet Earth. I’ll visit one city per day, visiting each city once.”
            #2 said, “Quite a year!”
            Liberty turned her map over; on the other side was a large number table. “Here’s a list of  those cities, and the distances between them. Which tour is shortest?”
            #2 frowned. He pushed a button on the control panel. It flickered its lights,  beeped, and issued a printed paper tape. #2 read it and said, “That is difficult to determine. You have assigned us the Traveling Salesman Problem for 365 nodes. The total number of possible tours is 2.5 times 10778. Checking all of these routes for the shortest one would be time-consuming, to say the least.”
            “Then you had better get started right away.”
            “We would prefer a more efficient algorithm.”
            Liberty asked, “Do you have one?”
            #2 said, “Not as yet.”
            “Maybe there isn’t any.”
            “That possibility too has not yet been ruled out.” #2 sighed, then pushed a button on the panel. “A portion of the system has been assigned to the task of checking all the routes. It will report back to us as soon as its findings are complete. Next question, please,” #2 said irritably.
            “You don’t have the best route yet? Too bad,” said  Liberty. “Would you like to know mine?”
            “Yes, we would very much indeed like to know what route you plan to take,” said  #2.
            “Here it is!” she said. And she produced a thin computer printout which she dropped lightly at #2's feet. “That’s a pair of large numbers,” she explained. “The first number encodes the route, and the second one is the encryption key.”
            “Then this shouldn’t be hard to decode,” #2 said as he bent down to pick up the printout.
            “It shouldn’t be,” said Miss Liberty, “if you had the decryption key-number. But you only have the encryption key there. You can only make code, not break it.”
            #2 held the thin printout and said with dismay. “A dual-key public encryption scheme.”
            “So now you can write me any messages you want to, and be sure that none of those nasty little spies are eavesdropping!” said Miss Liberty. “Isn’t that a relief?”
            “How do we decode this?” #2 demanded.
            “That’s easy. To crack the code, you just have to factor the second number. It’s a product of two large prime numbers. They’re only twenty thousand digits long,” said Miss Liberty.
            #2 roared, “Twenty thousand digits!”
            “It’s a simple program; it’ll just take awhile, that’s all!”
            “The other program will finish sooner!”
            “Don’t you have any factoring programs fast enough?”
            “No.” #2 glared at Miss Liberty; then he sighed with resignation. He fed the thin printout into the control panel and pushed a button.

            Then the lights went out.
            In the sudden darkness we heard #2 say, “This program is jammed. Consult supervisor.”

            * click *

            Thus Miss Liberty outnumbered #2 with the Traveling Salesman Problem and a large number factorization.
            #2 said, “You now have Full Access to JOV. Beware, Master! She’s a glitch! Burn her!”   

No comments:

Post a Comment