Mathematics, Computing, and Arithmetic

We have remarked earlier that actually doing cryptography requires combining mathematics and computing. In this chapter we describe several algorithms and computational tricks that make it possible to do the discrete mathematics that is cryptography on computers that have not necessarily been designed to provide robust support for discrete mathematics. This chapter covers a few of these tricks and algorithms necessary for understanding how one might actually do cryptography in the real world. The first set of tricks has been used extensively in testing integers for primality, using the bit patterns of the integers to eliminate the need for modular reduction. Multiprecise arithmetic is needed for much of modern cryptography, with modular reduction and multiplication dominating the cost of arithmetic. Multiplication itself is done with fast methods like the FFT, which we cover here, and reduction can be dealt with by Montgomery multiplication, which essentially extends the Mersenne prime trick to all integer moduli.