Cryptography Reference
In-Depth Information
12
≡
3mod9
,
3 is a valid remainder since 9
|
(12
−
3)
12
≡
21 mod 9
,
21 is a valid remainder since 9
|
(21
−
3)
12
≡−
6mod9
,
−
6 is a valid remainder since 9
|
(
−
6
−
3)
where the “
x
|
y
” means “
x
divides
y
”. There is a system behind this behavior. The set
of numbers
{
...,
−
24
,
−
15
,
−
6
,
3
,
12
,
15
,
24
,...
}
form what is called an
equivalence class
. There are eight other equivalence classes
for the modulus 9:
{
...,
−
27
,
−
18
,
−
9
,
0
,
9
,
18
,
27
,...
}
{
...,
−
26
,
−
17
,
−
8
,
1
,
10
,
19
,
28
,...
}
.
{
...,
−
19
,
−
10
,
−
1
,
8
,
17
,
26
,
35
,...
}
All Members of a Given Equivalence Class Behave Equivalently
For a given modulus
m
, it does not matter which element from a class we choose
for a given computation. This property of equivalent classes has major practical
implications. If we have involved computations with a fixed modulus — which is
usually the case in cryptography — we are free to choose the class element that
results in the easiest computation. Let's look first at an example:
Example 1.8.
The core operation in many practical public-key schemes is an expo-
nentiation of the form
x
e
mod
m
, where
x
,
e
,
m
are very large integers, say, 2048 bits
each. Using a toy-size example, we can demonstrate two ways of doing modular ex-
ponentiation. We want to compute 3
8
mod 7. The first method is the straightforward
approach, and for the second one we switch between equivalent classes.
3
8
= 6561
7 + 2
Note that we obtain the fairly large intermediate result 6561 even though we
know that our final result cannot be larger than 6.
≡
2 mod 7, since 6561 = 937
·
Here is a much smarter method: First we perform two partial exponentiations:
3
8
= 3
4
3
4
= 81
·
·
81
We can now replace the intermediate results 81 by another member of the same
equivalence class. The smallest positive member modulo 7 in the class is 4 (since
81 = 11
·
7 + 4). Hence:
3
8
= 81
·
81
≡
4
·
4 = 16 mod 7
