Page 308 - Discrete Mathematics and Its Applications

4.5 Applications of Congruences 287

2
66. Find all solutions of the congruence x ≡ 16 (mod 105). 67. Describe a brute force algorithm for solving the discrete
[Hint: Find the solutions of this congruence modulo 3, logarithm problem and find the worst-case and average-
modulo 5, and modulo 7, and then use the Chinese re- case time complexity of this algorithm.
mainder theorem.]

4.5 Applications of Congruences

Congruences have many applications to discrete mathematics, computer science, and many
other disciplines. We will introduce three applications in this section: the use of congruences
to assign memory locations to computer files, the generation of pseudorandom numbers, and
check digits.
Suppose that a customer identification number is ten digits long. To retrieve customer files
quickly, we do not want to assign a memory location to a customer record using the ten-digit
identification number. Instead, we want to use a smaller integer associated to the identification
number. This can be done using what is known as a hashing function. In this section we will
show how we can use modular arithmetic to do hashing.
Constructing sequences of random numbers is important for randomized algorithms, for
simulations, and for many other purposes. Constructing a sequence of truly random numbers is
extremely difficult, or perhaps impossible, because any method for generating what are supposed
to be random numbers may generate numbers with hidden patterns. As a consequence, methods
have been developed for finding sequences of numbers that have many desirable properties of
random numbers, and which can be used for various purposes in place of random numbers.
In this section we will show how to use congruences to generate sequences of pseudorandom
numbers.The advantage is that the pseudorandom numbers so generated are constructed quickly;
the disadvantage is that they have too much predictability to be used for many tasks.
Congruences also can be used to produce check digits for identification numbers of various
kinds, such as code numbers used to identify retail products, numbers used to identify books,
airline ticket numbers, and so on. We will explain how to construct check digits using congru-
ences for a variety of types of identification numbers. We will show that these check digits can
be used to detect certain kinds of common errors made when identification numbers are printed.

Hashing Functions

The central computer at an insurance company maintains records for each of its customers.
How can memory locations be assigned so that customer records can be retrieved quickly? The
solution to this problem is to use a suitably chosen hashing function. Records are identified
using a key, which uniquely identifies each customer’s records. For instance, customer records
are often identified using the Social Security number of the customer as the key. A hashing
function h assigns memory location h(k) to the record that has k as its key.
In practice, many different hashing functions are used. One of the most common is the
function

h(k) = k mod m

where m is the number of available memory locations.
Hashing functions should be easily evaluated so that files can be quickly located. The
hashing function h(k) = k mod m meets this requirement; to find h(k), we need only compute
the remainder when k is divided by m. Furthermore, the hashing function should be onto, so that
all memory locations are possible. The function h(k) = k mod m also satisfies this property.