Page 313 - Discrete Mathematics and Its Applications

292 4 / Number Theory and Cryptography

10
These last two congruences hold because i=1 i ≡ 0 (mod 10) and 11 | ja, because 11 | j
x
and 11 | a. We conclude that y 1 y 2 ...y 10 is not a valid ISBN. So, we have detected the single
error.
Now suppose that two unequal digits have been transposed. It follows that there are distinct
integers j and k such that y j = x k and y k = x j , and y i = x i for i = j and i = k. Hence,

10 10

iy i = ix i + (jx k − jx j ) + (kx j − kx k ) ≡ (j − k)(x k − x j ) ≡ 0 (mod 11),
i=1 i=1
10
because i=1 i ≡ 0 (mod 10) and 11 | (j − k) and 11 | (x k − x j ). We see that y 1 y 2 ...y 10
x
is not a valid ISBN. Thus, we can detect the interchange of two unequal digits.

Exercises

1. Which memory locations are assigned by the hashing 7. What sequence of pseudorandom numbers is gener-
function h(k) = k mod 97 to the records of insurance ated using the pure multiplicative generator x n+1 =
company customers with these Social Security numbers? 3x n mod 11 with seed x 0 = 2?
a) 034567981 b) 183211232 8. Write an algorithm in pseudocode for generating a se-
c) 220195744 d) 987255335 quence of pseudorandom numbers using a linear congru-
ential generator.
2. Which memory locations are assigned by the hashing
function h(k) = k mod 101 to the records of insurance The middle-square method for generating pseudorandom
company customers with these Social Security numbers? numbers begins with an n-digit integer. This number is
squared, initial zeros are appended to ensure that the result
a) 104578690 b) 432222187
has 2n digits, and its middle n digits are used to form the next
c) 372201919 d) 501338753
number in the sequence. This process is repeated to generate
3. A parking lot has 31 visitor spaces, numbered from 0 to additional terms.
30.Visitors are assigned parking spaces using the hashing 9. Find the first eight terms of the sequence of four-digit
function h(k) = k mod 31, where k is the number formed pseudorandom numbers generated by the middle square
from the first three digits on a visitor’s license plate. method starting with 2357.
a) Which spaces are assigned by the hashing function to 10. Explain why both 3792 and 2916 would be bad choices
cars that have these first three digits on their license for the initial term of a sequence of four-digit pseudoran-
plates: 317, 918, 007, 100, 111, 310? dom numbers generated by the middle square method.
b) Describe a procedure visitors should follow to find a The power generator is a method for generating pseudoran-
free parking space, when the space they are assigned dom numbers. To use the power generator, parameters p and d
is occupied. are specified, where p is a prime, d is a positive integer such
that p | d, and a seed x 0 is specified. The pseudorandom num-
Another way to resolve collisions in hashing is to use double
hashing. We use an initial hashing function h(k) = k mod p bers x 1 ,x 2 ,... are generated using the recursive definition
d
n
where p is prime. We also use a second hashing function x n+1 = x mod p.
g(k) = (k + 1) mod (p − 2).When a collision occurs, we use 11. Find the sequence of pseudorandom numbers generated
a probing sequence h(k, i) = (h(k) + i · g(k)) mod p. by the power generator with p = 7, d = 3, and seed
x 0 = 2.
4. Use the double hashing procedure we have described with 12. Find the sequence of pseudorandom numbers generated
p = 4969 to assign memory locations to files for em- by the power generator with p = 11, d = 2, and seed
ployees with social security numbers k 1 = 132489971, x 0 = 3.
k 2 = 509496993, k 3 = 546332190, k 4 = 034367980,
k 5 = 047900151, k 6 = 329938157, k 7 = 212228844, 13. Suppose you received these bit strings over a communi-
k 8 = 325510778, k 9 = 353354519, k 10 = 053708912. cations link, where the last bit is a parity check bit. In
which string are you sure there is an error?
5. What sequence of pseudorandom numbers is gener-
a) 00000111111
ated using the linear congruential generator x n+1 =
b) 10101010101
(3x n + 2) mod 13 with seed x 0 = 1? c) 11111100000
6. What sequence of pseudorandom numbers is gener- d) 10111101111
ated using the linear congruential generator x n+1 = 14. Prove that a parity check bit can detect an error in a string
(4x n + 1) mod 7 with seed x 0 = 3? if and only if the string contains an odd number of errors.