3.1. Introduction

Now that we have studied the properties of important mathematical objects that play vital roles in public-key cryptology, it is time to concentrate on the algorithmic and implementation issues for working with these objects. We need well-defined schemes (data structures) to represent these objects and well-defined procedures (algorithms) to manipulate them. While a theoretical analysis of the performance of our data structures and algorithms is of great concern, it still leaves us in the abstract domain. In the long run, one has to translate the abstract statements in the algorithms to machine codes that the computer understands, and this is where the implementation tidbits come into picture. It is our personal experience that a naive implementation of an algorithm may run hundred times slower than a carefully optimized implementation of the same algorithm. In certain specific applications (like those based on smart cards), where memory is a scarce resource, one should also pay attention to the storage requirements of the data structures and code segments. This chapter is an introduction to all these specialized topics.

Before we proceed further, certain comments are in order. In this book, we describe algorithms using a pseudocode that closely resembles the syntax of the programming language C. The biggest difference between C and our pseudocode is that we have given preference to mathematical notations in place of C syntax. For example, = means equality in our codes, whereas assignment is denoted by :=. Similarly, our while and for loops look more human-readable, for example, for i = 0, 1, . . . , m – 1 instead of C’s for (i=0; i<m; i++). In order to understand our pseudocode, a knowledge of C (or a similar programming language) is helpful, but not essential, on the part of the reader.