Cryptography Reference
In-Depth Information
Calculation in residue class rings can be made clearer by employing
composition tables
, which we present in Tables 5-1 and 5-2 for the operations “
+
”
and “
·
Z
”in
5
.
Table 5-1. Composition table for addition modulo 5
01234
+
0
01234
1
12340
2
23401
3
34012
4
40123
Table 5-2. Composition table for multiplication modulo 5
·
01234
0
00000
1
01234
2
02413
3
03142
4
04321
The fact that the set of residue classes is finite gives the nice advantage
over infinite structures, such as the ring of integers, that the representation of
the results of arithmetic expressions within a computer program will not cause
overflow if in forming residues a suitable class representative is chosen. This
operation, as executed for example by the function
mod_l()
, is called
reduction
(modulo
m
). We can thus calculate to our hearts' content with the bounded
representation of numbers and the functions of the FLINT/C package within a
complete residue system modulo
m
,solongaswehave
m
N
max
. We always
choose positive representatives and rely on nonnegative residue systems. Because
of these properties of residue classes the FLINT/C package does very well with the
CLINT
representation of large numbers, except for a few situations, which we shall
discuss in some detail.
So much for the theory of the arithmetic of residue classes. Now we shall
develop our functions for modular arithmetic. We first recall the functions
mod_l()
and
mod2_l()
from Section 4.3, which return the remainder of a reduction modulo
m
, respectively modulo
2
k
, and we shall deal in turn with modular addition
and subtraction, as well as modular multiplication and squaring. Because of its
particular complexity, we devote a separate chapter to modular exponentiation.
≤
