|Previous||Table of Contents||Next|
Michael Garey and David Johnson compiled a list of over 300 NP-complete problems . Here are just a few of them:
This isnt a book on number theory, so Im 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].
You all learned modular arithmetic in school; it was called clock arithmetic. Remember these word problems? If Mildred says shell be home by 10:00, and shes 13 hours late, what time does she get home and for how many years does her father ground her? Thats arithmetic modulo 12. Twenty-three modulo 12 equals 11.
Another way of writing this is to say that 23 and 11 are equivalent, modulo 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, PASCALs 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: Its 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.
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,
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 doesnt make much difference now, but it will when youre working with 200-bit numbers.
For example, if you want to calculate a8 mod n, dont use the naïve approach and perform seven multiplications and one huge modular reduction:
Instead, perform three smaller multiplications and three smaller modular reductions:
By the same token,
|Previous||Table of Contents||Next|