Chapter 4: Number Theory and Cryptography

A parking lot has 31 visitor spaces, numbered from 0 to

30. Visitors are assigned parking spaces using the hashing

function, $\mathbf{h}\mathbf{\left(}\mathbf{k}\mathbf{\right)}\mathbf{=}\mathbf{k}\mathbf{mod}\mathbf{31}$where k is the number formed

from the first three digits on a visitor’s license plate.

a) Which spaces are assigned by the hashing function to

cars that have these first three digits on their license

plates:$\mathbf{317}\mathbf{,}\mathbf{918}\mathbf{,}\mathbf{007}\mathbf{,}\mathbf{100}\mathbf{,}\mathbf{111}\mathbf{,}\mathbf{310}$?

b) Describe a procedure visitors should follow to find a

free parking space, when the space they are assigned

is occupied.

Encrypt the message WATCH YOUR STEP by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters.

a) f(p)=(p+14) mod 26

b) f(p)=(14 p+21) mod 26

c) f(p)=(-7 p+1) mod 26

Prove that part\((ii)\)of Theorem\(1\)is true.

Convert the binary expansion of each of these integers to a decimalexpansion.

1. \({(1\;\;{\rm{1111)}}_2}\)
2. \({(10{\rm{ 0000 0001)}}_2}\)
3. \({(1{\rm{ 0101 0101)}}_2}\)
4. \({(110{\rm{ 1001 0001 0000)}}_2}\)

By inspection (as discussed prior to Example 1 ), find an inverse of 4 modulo 9 .

Find the prime factorization of each of these integers.

d.) 1001 e.) 1111 f.) 909,090

Show that if $\mathrm{a}\equiv \mathrm{b}(\mathrm{mod}\mathrm{m})\mathrm{and}\mathrm{c}\equiv \mathrm{d}(\mathrm{mod}\mathrm{m})$, then $a+c\equiv b+d(modm)$.

Find four numbers congruent 5modulo 17.

Find the two’s complement representations, using bit strings of length six, of the following integers.

a) 22 b) 31 c) −7 d) −19

Using the method followed in Example 17, express the greatest common divisor of each of these pairs of integers as a linear combination of these integers.