Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) (Publisher: John Wiley & Sons, Inc.) Author(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book:
Previous | Table of Contents | Next
NP-Complete Problems Michael Garey and David Johnson compiled a list of over 300 NP-complete problems [600]. Here are just a few of them: — Traveling Salesman Problem. A traveling salesman has to visit n different cities using only one tank of gas (there is a maximum distance he can travel). Is there a route that allows him to visit each city exactly once on that single tank of gas? (This is a generalization of the Hamiltonian Cycle problem—see Section 5.1.) — Three-Way Marriage Problem. In a room are n men, n women, and n clergymen (priests, rabbis, whatever). There is also a list of acceptable marriages, which consists of one man, one woman, and one clergyman willing to officiate. Given this list of possible triples, is it possible to arrange n marriages such that everyone is either marrying one person or officiating at one marriage? — Three-Satisfiability. There is a list of n logical statements, each with three variables. For example: if (x and y) then z, (x and w) or (not z), if ((not u and not x) or (z and (u or not x))) then (not z and u) or x), and so on. Is there a truth assignment for all the variables that satisfies all the statements? (This is a special case of the Satisfiability problem previously mentioned.) ### 11.3 Number Theory This isn’t a book on number theory, so I’m just going to sketch a few ideas that apply to cryptography. If you want a detailed mathematical text on number theory, consult one of these books: [1430, 72, 1171, 12, 959, 681, 742, 420]. My two favorite books on the mathematics of finite fields are [971, 1042]. See also [88, 1157, 1158, 1060]. Modular Arithmetic You all learned modular arithmetic in school; it was called “clock arithmetic.” Remember these word problems? If Mildred says she’ll be home by 10:00, and she’s 13 hours late, what time does she get home and for how many years does her father ground her? That’s arithmetic modulo 12. Twenty-three modulo 12 equals 11. (10 + 13) mod 12 = 23 mod 12 = 11 mod 12 Another way of writing this is to say that 23 and 11 are equivalent, modulo 12: 23 ≡ 11 (mod 12) Basically, a ≡ b (mod n) if a = b + kn for some integer k. If a is non-negative and b is between 0 and n, you can think of b as the remainder of a when divided by n. Sometimes, b is called the residue of a, modulo n. Sometimes a is called congruent to b, modulo n (the triple equals sign, ≡, denotes congruence). These are just different ways of saying the same thing. The set of integers from 0 to n - 1 form what is called a complete set of residues modulo n. This means that, for every integer a, its residue modulo n is some number from 0 to n - 1. The operation a mod n denotes the residue of a, such that the residue is some integer from 0 to n - 1. This operation is modular reduction. For example, 5 mod 3 = 2. This definition of mod may be different from the definition used in some programming languages. For example, PASCAL’s modulo operator sometimes returns a negative number. It returns a number between -(n - 1) and n - 1. In C, the % operator returns the remainder from the division of the first expression by the second; this can be a negative number if either operand is negative. For all the algorithms in this book, make sure you add n to the result of the modulo operator if it returns a negative number. Modular arithmetic is just like normal arithmetic: It’s commutative, associative, and distributive. Also, reducing each intermediate result modulo n yields the same result as doing the whole calculation and then reducing the end result modulo n. a + b) mod n = ((a mod n) + (b mod n)) mod n (a - b) mod n = ((a mod n) - (b mod n)) mod n (a*b) mod n = ((a mod n)*(b mod n)) mod n (a*(b + c)) mod n = (((a*b) mod n) + ((a*c) mod n)) mod n Cryptography uses computation mod n a lot, because calculating discrete logarithms and square roots mod n can be hard problems. Modular arithmetic is also easier to work with on computers, because it restricts the range of all intermediate values and the result. For a k- bit modulus, n, the intermediate results of any addition, subtraction, or multiplication will not be more than 2k- bits long. So we can perform exponentiation in modular arithmetic without generating huge intermediate results. Calculating the power of some number modulo some number, ax mod n, is just a series of multiplications and divisions, but there are speedups. One kind of speedup aims to minimize the number of modular multiplications; another kind aims to optimize the individual modular multiplications. Because the operations are distributive, it is faster to do the exponentiation as a stream of successive multiplications, taking the modulus every time. It doesn’t make much difference now, but it will when you’re working with 200-bit numbers. For example, if you want to calculate a8 mod n, don’t use the naïve approach and perform seven multiplications and one huge modular reduction: (a*a*a*a*a*a*a*a) mod n Instead, perform three smaller multiplications and three smaller modular reductions: ((a2 mod n)2 mod n)2 mod n By the same token, a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n
Previous | Table of Contents | Next
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.