Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

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.)

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 2*k-* bits long. So we can perform exponentiation in modular arithmetic without generating huge intermediate results. Calculating the power of some number modulo some number,

*a*mod^{x}*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 *a ^{8}* mod

- (
*a*a*a*a*a*a*a*a*) mod*n*

Instead, perform three smaller multiplications and three smaller modular reductions:

- ((
*a*mod^{2}*n*)^{2}mod*n*)2 mod*n*

By the same token,

*a*mod^{16}*n*= (((*a*mod^{2}*n*)^{2}mod*n*)^{2}mod*n*)^{2}mod*n*

Previous | Table of Contents | Next |