APPENDIX 6.1: IMPLEMENTATION OF MODULAR ARITHMETIC
The prime moduli in the above examples are of a special type (called generalized Mersenne numbers) for which modular multiplication can be carried out more efficiently than in general. This appendix provides the rules for implementing this faster arithmetic, for each of the prime moduli appearing in the examples.
The usual way to multiply two integers (mod m) is to take the integer product and reduce it (mod m). One therefore has the following problem: given an integer A less than m2, compute
In general, one must obtain B as the remainder of an integer division. If m is a generalized Mersenne number, however, then B can be expressed as a sum or difference (mod m) of a small number of terms. To compute this expression, one can evaluate the integer sum or difference and reduce the result modulo m. The latter reduction can be accomplished by adding or subtracting a few copies of m.
The prime moduli p for each of the five example curves is a generalized Mersenne number.
49
