Cryptography Reference
In-Depth Information
An important corollary to the definition is that, if
a
≡
b
(mod
m
), then we know that
m
divides
(a
-
b),
and
therefore we know that there is some integer
k
such that
mk
=
a
-
b
, or
a
=
b
+
km.
As a quick, historical example, computers before the year 2000 had a problem: They would store only the
last two digits of the year, since it was assumed that all dates were in the 1900s. This was known as the Y2K
problem. Since we consider only two digits, this is the same as considering all numbers modulo 100 (since, if
we take any number's remainder when divided by 100, we would be left with the last two decimal digits). The
problem then arose that 2000 ≡ 1900 ≡ 0 (mod 100). This caused some computer programs to have erratic be-
havior, such as suddenly transition from the year 1999 to 1900, with unpredictable results.
A similar problem might occur again in 2038. It turns out that the POSIX standard section 4.14 and standard
header file
<sys/time.h>'s time_t
construct [4] use the original time definition from the first edi-
tion of UNIX [12], which measures time as a signed 32-bit integer containing the number of seconds since 1
January 1970. This gives us a total of 2,147,483,647 seconds to work with, so that we are working modulo
2,147,483,648. When we divide this by 60 seconds per minute, 60 minutes per hour, 24 hours per day, and
365.25 days per year,
2
the result is a little more than 68 years from 1970, or sometime in 2038, before the con-
gruence between 0 and 2,147,483,648 kicks us back to 1970.
It also turns out that numbers that are congruent with a certain modulus can be used interchangeably for
many mathematical operations also in that modulus. These operations include addition, subtraction, and multi-
plication, but
not
division. These three operations work exactly like they do with normal numbers: Addition is
still addition, and 5 + 5 is still going to be 10 modulo 20, but it will be congruent to an infinite number of other
integers in the modulus, including 30, 50, and even -10.
For example, in modulo 10, 12 and 2 are congruent to each other. If we performed, say, 2 + 2 mod 10, we
know that the answer is congruent to 4 modulo 10. And if we compute 12 + 12 modulo 10, we know that we
will get 24, which is congruent to 4 as well. Subtraction and multiplication work similarly.
But division is not so straightforward. For example, let's take modulo 10 again. Computing 20 ÷ 5 = 4, if
division worked as we expect it to, we should be able to replace 20 with 0 and then divide by 10, since 20 = 0
(mod 10). However, in that case, we get 0, which is not congruent to 4.
A little more terminology: A set of numbers that are all congruent to each other in a particular modulus are
often grouped together in a set called its
congruence class
or
residue class.
As such, any particular number is
referred to as a
residue.
Furthermore, if we have a
complete set of residues
(CSR), then every integer will be congruent to
exactly
one residue in the set. This can work as a basis to do any arithmetic for the modulus. All operations can be com-
puted for the elements of the CSR, and the results written also as elements of the CSR. For example, a complete
set of residues for modulo 10 is
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
which we will often use as our standard CSR. However, another complete set is
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
or even
{101, 102, 103, 104, 105, 106, 107, 108, 109, 110}
There is another important set of residues we need to discuss: a
reducedsetofresidues
(RSR). With a CSR,
we have every integer congruent to exactly one element of the CSR. With an RSR, however, we only care about
numbers that are relatively prime to the modulus. A set of numbers that has the property that every integer rel-
atively prime to the modulus is congruent to exactly one of the numbers in the set is an RSR.
For example, say we have a CSR of 10 again, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. We calculate the RSR by going
through each item in the list and deleting every number that is
not
relatively prime to 10. Since 10 = 2 × 5, then
Search WWH ::
Custom Search