Cryptography Reference
In-Depth Information
of 187. Note also that 46 is a divisor of 46, and 1 is a divisor of 10023. Indeed, every
number has at least two divisors, namely the number itself and 1. Most numbers
have more divisors than that.
A
prime
is a number that has no divisors other than itself and 1. For example,
17 is prime because 17 and 1 are the only numbers that divide into 17. Also 2
is a prime, so is 3, and 5, and 7. On the other hand 18 is not prime because
2, 3, 6 and 9 are also divisors of 18. Primes have many special mathematical
properties, which is why they form the basis for so many different cryptographic
algorithms.
GREATEST COMMON DIVISORS
The
greatest common divisor
(usually abbreviated to gcd) of two numbers is the
largest whole number that divides neatly into both numbers without leaving a
remainder. In other words, the gcd of
a
and
b
is the largest number that is a
divisor of both
a
and
b
.
For example, the gcd of 14 and 21 is 7, since 7 is the largest divisor of both 14
and 21. We normally write this as:
gcd(14
,
21)
=
7
.
Similarly, gcd(6
2, since 2 is the largest divisor of both 6 and 8.
Every pair of numbers has a greatest common divisor. Since 1 is a divisor of
every number, it follows that there is always at least one common divisor. In some
cases 1 is the greatest common divisor, but for many pairs of numbers there is a
larger common divisor than 1.
,
8)
=
COPRIMES
We say that two numbers are
coprime
if their greatest common divisor is 1. In other
words, two numbers are coprime if the only divisor that they have in common is
the number 1. Or, using our gcd notation, two numbers
a
and
b
are coprime if
gcd(
a
,
b
)
=
1. For example, 42 and 55 are coprime. But 42 and 56 are not coprime,
since 2 divides into 42 and 56 (as do many other numbers).
Primality and coprimality are different concepts. Primality is ameasure applied
to a single number on its own. Coprimality is a measure applied to two numbers
to compare them with one another. However, it is true that two different primes
are always coprime to one another.
A.3.2
Multiplicative inverses
Before considering division in modular arithmetic, we need to reconsider what
division means in normal arithmetic.
