Cryptography Reference
In-Depth Information
By replacing January to December with the numbers 0 to 11, we can write these
calculations as:
0
+
3
=
3
9
+
4
=
1
This is modulo 12 arithmetic. There are many other examples of this type of
'unconscious' use of modular arithmetic . For example, the 24-hour clock provides
an example of modulo 24 arithmetic.
A.2.2
Modular numbers
We can perform modular arithmetic using any positive integer as the modulus,
where by
positive integer
we mean a whole number that is bigger than 0 (in other
words a number such as 2, 18, 754, etc.). When working modulo
n
(mod
n
), where
n
is some positive integer which we call the
modulus
, the only numbers that we
deal with are:
0
,
1
,
2
,
3
,...,
n
−
1
.
Thus, instead of having numbers that go on forever, when working modulo
n
we
only have
n
different numbers to work with. For example, mod 6 arithmetic only
uses the numbers 0, 1, 2, 3, 4 and 5, andmod 359 arithmetic only uses the numbers
0
358. Using modular arithmetic we will later see that
we can add, subtract and multiply numbers. So long as the answer is less than the
modulus, these operations are just the same as if there was nomodulus being used.
For example, when working modulo 358, 57
,
1
,
2
,
3
,...,
355
,
356
,
357
,
158. However, we need to
consider what happens when the answer takes us beyond the modulus value.
+
101
=
ADDING MULTIPLES OF THE MODULUS
First, let us consider what happens if we add two numbers modulo
n
and end
up with
n
itself. For example, when working modulo 7, what happens when we
compute3+4?Weknow that 3
+
4
=
7, but in modulo 7 arithmetic there is no
number 7.
Recall the example based on days of the week. When working modulo 7 we see
that asking 'what is 3 + 4?' in modulo 7 arithmetic is equivalent to asking 'what
day comes four days after Thursday?'. The answer is Monday, which is day 0, so:
3
+
4
=
0mod 7
.
The 'mod 7' at the end of the line indicates that we are performing the calculation
modulo 7. Unless it is clear from the context, it is important to include this
indicator, since the answer to 'what is 3 + 4?' depends verymuch on what modulus
we are working with.
