Cryptography Reference
In-Depth Information
The important lesson is that when working modulo
n
, adding
n
to a number
will not change it. Again, thinking of the days of the week example, seven days
after Tuesday it is Tuesday again:
2
+
7
=
2mod 7
.
In fact, 14 days after Tuesday it is Tuesday again:
2
+
14
=
2mod 7
.
Also, seven days before Tuesday is also Tuesday:
2
−
7
=
2mod 7
.
Thus, in modulo
n
arithmetic, the number
n
behaves just like 0 does for the
numbers that we normally use. This is an important principle of modular
arithmetic.
ONE NUMBER MODULO ANOTHER
Consider two numbers
a
and
n
, where
a
and
n
are both positive integers. Although
a
is a positive integer, suppose that we want to know what value
a
would take if
we considered it as a number modulo
n
. This question is often phrased as 'what
is the value of
a
modulo
n
'?
It is important to recognise that there will be an answer to this question. This is
because any number can be expressed uniquely modulo any other number. Since
we have just seen that in modulo
n
arithmetic all multiples of
n
are 0, we can see
that the answer to our question is that
a
will take the value that is the
remainder
when we divide
a
by
n
.
To see a simple example, let
a
5. We know that 5 is the same as
0 in modulo 5 arithmetic. Since 6 is just one more than 5, it follows that 6 will be
the same as 1 in modulo 5 arithmetic. This is just another way of saying that when
we divide 6 by 5 we get a remainder of 1. Thus 6 is equal to 1 when 6 is considered
as a number modulo 5. In other words,
=
6 and
n
=
6
=
1mod 5
.
Similarly, let
a
=
5417 and
n
=
7. We can divide 5417 by 7 using traditional
arithmetic to discover that:
5417
=
(773
×
7)
+
6
.
Since we know that 7
7)
will also be 0. Thus 5417 is equal to 6 when we work modulo 7, which we write:
=
0 when we are working modulo 7, it follows that (773
×
5417
=
6mod 7
.
Returning to our analogy, if we ask 'what day of the week is it 5417 days after
Wednesday?' we now know that in 5417 days it will be 6 days after Wednesday,
so it will be Tuesday!
