S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani39Fermat test(base a = 2)CompositesPassFail≈ 109primes≈ 20,000 compositesBefore primality test:all numbers ≤ 25 × 109After primality testPrimesRandomized algorithms: a virtual chapterSurprisingly—almost paradoxically—some of the fastest and most clever algorithms we haverely on chance: at specified steps they proceed according to the outcomes of random cointosses. These randomized algorithms are often very simple and elegant, and their output i scorrect with high probability. This success probability does n ot depend on the randomnessof the input; it only depends on the random choices made by the algorithm itself.Instead of devoting a special chapter to this topic, in this book we intersperse randomizedalgorithms at the chapters and sections where they arise most naturally. Furthermore,no specializ ed knowledge of probability is necessary to follow what is happening. You justneed to be familiar with the concept of probability, expected value, the expected numberof times we must flip a coin before getting heads, and the property known as “linearity ofexpectation.”Here are pointers to the major randomized algorithms in this book: One of the earliestand most dramatic examples of a randomized algorithm is the randomized primality test ofFigure 1.8. Hash ing is a general randomized data structure that supports inserts, deletes,and lookups and is described later in this chapter, in Section 1.5. Randomized algorithmsfor sorting and median finding are described in Chapter 2. A randomized algorithm for themin cut problem is described in the box on page 150. Randomization plays an important rolein heuristics as well; these are described in Section 9.3. And finally the quantum algorithmfor factoring (Section 10.7) works very much li ke a randomized algorithm, its output beingcorrect with high probability—except that it draws its randomness not from coin tosses, butfrom the superposition principle in quantum mechanics.Virtual exercises: 1.29, 1.34, 2.24, 9.8, 10.8.1.4 CryptographyOur next topic, the Rivest-Shamir-Adelman (RSA) cryptosystem, uses all the ideas we haveintroduced in this chapter! It derives very strong guarantees of security by ingeniously ex-ploiting the wide gul f between the polynomial-time computability of certain number-theoretictasks (modular exponentiation, greatest common divisor, primality testing) and the intractabil-ity of others (factoring).40AlgorithmsThe typical setting for cryptography can be described via a cast of three characters: Aliceand Bob, who wish to communicate in private, and Eve, an eavesdropper who will go to greatlengths to fi nd out what they are saying. For concreteness, let’s say Alice wants to send aspecific message x, written in binary (why not), to her friend Bob. She encodes it as e(x),sends it over, and then Bob applies his decryption function d(·) to decode it: d(e(x)) = x. Heree(·) and d(·) are appropriate transformations of the messages.EveBobAliceEncoderDecoderx x = d(e(x))e(x)Alice and Bob are worried that the eavesdropper, Eve, will intercept e(x): for instance, shemight be a sniffer on the network. But ideally the encryption function e(·) is so chosen thatwithout knowing d(·), Eve cannot do anything with the information she has picked up. Inother words, knowing e(x) tells her little or nothing about what x might be.For centuries, cryptography was based on what we now call private-key protocols. In sucha scheme, Alice and Bob meet beforehand and together choose a secret codebook, with whichthey encrypt all future correspondence between them. Eve’s only hope, then, is to collect someencoded messages and use them to at least partially figure out the codebook.Public-key schemes such as RSA are sig nificantly more subtle and tricky: they allow Aliceto send Bob a message without ever having m et him before. This almost sounds impossible,because in this scenario there is a symmetry between Bob and Eve: why should Bob haveany advantage over Eve in terms of being able to understand Alice’s message? The centralidea behind the RSA cryptosystem is that using the dramatic contrast between factoring andprimality, Bob is able to implement a digital lock, to which only he has the key. Now bymaking this digital lock pub lic, he gives Alice a way to send him a secure message, which onlyhe can open. M oreover, this is exactly the scenario that comes up in Internet commerce, forexample, when you wish to send your credit card number to some company over the Internet.In the RSA protocol, Bob need only perform the simplest of calcula tions, such as multi-plication, to implement hi s digital lock. Similarly Alice and Bob need only perform simplecalculations to lock and unlock the message respectively—operations that any pocket com-puting device could handle. By contrast, to unlock the message without the key, Eve mustperform operations like factoring large numbers, which requires more computational powerthan would be afforded by the world’s most powerful computers combined. This compellingguarantee of security explains why the RSA cryptosystem is such a revolutionary develop-ment in cryptography.S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani41An application of number theory?The renowned mathematician G. H. Hardy once declared of his work: “I have never doneanything useful.” Hardy was an expert in the theory of numbers, which has l ong been re-garded as one of the purest areas of mathematics, untarnished by material motivation andconsequence. Yet the work of thousands of number theorists over the centuries, Hardy’s in-cluded, is now crucial to the operation of Web browsers and cell phones and to the securityof financial transactions worldwide.1.4.1 Private-key schemes: one-time pad and AESIf Alice wants to transmit a n important private message to Bob, it would be wise of her toscramble it with an encryption function,e : !messages" → !encoded messages".Of course, this function must be invertible—for decoding to be possible—and is therefore abijection. Its inverse is the decryption function d(·).In the one-time pad, Alice and Bob meet beforehand and secretly choose a bin ary stringr of the sa m e length—say, n bits—as the important message x that Al ice will later send.Alice’s encryption function is then a bitwise exclusive-or, er(x) = x ⊕ r: each position in theencoded message is the exclusive-or of the corresponding positions in x and r. For instance,
View Full Document