Cryptography Reference
In-Depth Information
ADDITION, SUBTRACTION AND MULTIPLICATION
The good news is that the basic arithmetic operations of addition, subtraction and
multiplication behave just as we would expect them to. In other words, we can add
numbers, subtract them, or multiply them, just as we would 'normal' numbers.
We just need to remember to reduce the answer modulo
n
. Thus, for example:
3
+
3
=
6
=
1mod 5
5
+
4
=
9
=
2mod 7
3
−
5
=−
2
=
7mod 9
4
×
5
=
20
=
2mod 18
3
×
3
×
3
=
27
=
3mod 4
.
Importantly, division is intentionally left out of this list because it does not work
in quite the same way as it does for normal numbers. There is a way to deal with
division, but we discuss this later.
0
×
6
=
0mod 7
MODULAR REDUCTION: BEFORE OR AFTER?
One issue worth clarifying when doing a calculation such as 15
+
20mod 6 is
whether we should reduce 15 and 20 modulo 6 before, or after, they have been
added together. Fortunately, it does not matter, since will still get the same answer.
This is best seen by example:
1.
Add then reduce
: We first compute 15
+
20
=
35 and then note that 35
=
5mod 6.
2.
Reduce then add
: We first compute 15
5mod 6. So 15
+
20
=
=
3mod 6, and then 20
=
2mod 6.
Now we add the answers, in other words 15
+
20
=
3
+
2
=
5mod 6.
This section contains the remaining mathematical tools that we need in order to
understand the RSA cryptosystem.
A.3.1
Primes and coprimes
Before we learn how to 'divide' in modular arithmetic, we need to explore the
concept of division in a bit more detail.
PRIMES
A
divisor
of a number is any number that divides into it 'neatly' with no remainder
left over. For example, 3 is a divisor of 6, 5 is a divisor of 145, and 17 is a divisor
