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.

For certain implementations, we assume that the target machine carries out 32-bit 2’s-complement arithmetic. This is indeed true for most modern PCs and personal work stations. By the term word, we mean a 32-bit unit in the computer memory. We will also assume that the compiler provides facilities for storing and doing arithmetic with unsigned 64-bit integers. Though this is not an ANSI C feature, most popular compilers used today do support this built-in data type (Examples: unsigned __int64 for the Microsoft Visual C++ Compiler and unsigned long long for the GNU C Compiler). Though it is apparently desirable to be more generic and to avoid these specific assumptions on the part of the machine and the compiler, our exposition highlights the power of fine-tuning based on the knowledge of the underlying system.