160.212 Discrete Mathematics Assignment 3 Semester One, 2022

1. Alex and Bo use RSA public key cryptography to encrypt the messages they send each other. Alex’s public key is

(n, e) = (2773, 81),

and Bo’s public key is

(n, e) = (2279, 173).

(a) Bo wants to send Alex the message 36. Use Alex’s public key to encrypt the message. (b) Bo receives the message 64 from Alex in reply.

i. Find the prime factorisation of 2279.

ii. Use the prime factorisation and the Euclidean algorithm to find Bo’s decryption key.

iii. Decrypt the message Bo received from Alex.

You may use a computer or the internet to find the prime factorisation — searching for eg “prime factors of 2279” will give it to you. For the encryption and decryption calculations, show all steps necessary to find the answer using a simple scientific calculator.

2. For each of the following binary codes, (i) find the minimum distance, (ii) state whether it can correct, or can detect but not correct, single bit errors, (iii) determine if it is a group code.

(a)  C1  = {00000, 10101, 01001, 10010, 01110} S 勿2(5)

(b)  C2  = x e 勿2(5)  │ │(┌)              │(┐) x =  │(┌)  │(┐) 

(c)  C3  = ,x e 勿2(4)  │  ┐ x = ┌ 1(1) ┐、

3.  Consider the binary code C = NS(H) S 勿2(7), where

H =  ┌  ┐

│ 1   1   0   1   0   0   1 │ .

The following words are received:

a = 1100101,    b = 1001100,    c = 0010001.

Calculate the syndrome of each word to determine if it is a valid code word of C. In each case where you find an invalid string, correct if possible to the closest valid code word, and explain how you made the correction.  If it is not possible to correct, explain why not.

4. Determine with justification which pairs, if any, of the following graphs are isomorphic.

H

5. Use an adjacency matrix to find the number of directed walks of length 4 or less from v3 to v2  in the following directed graph.

6. Every vertex of a certain tree has degree 1 or 5.  If n vertices have degree 5, how many have degree 1?

7.  Of the two graphs ζ 1 , ζ2  drawn below, one has an Eulerian walk, and the other does not have an Eulerian walk, but it’s possible to add a single edge to the graph to get a new graph that does have an Eulerian walk.

(a) Identify which graph is which.

(b) For the graph that has an Eulerian walk:

i. Express the edge set as a union of disjoint circuits.

ii. Use your disjoint circuits to construct an Eulerian walk.

(c) For the graph that does not have an Eulerian walk:

i.  Specify a pair of vertices X, Y such that adding the edge {X, Y } to the graph gives a new graph that does have an Eulerian walk.

ii.  Give an Eulerian walk in the new graph.

A

A

d 

D

8. Let G be the graph ζ 1  in problem 7.

(a) Draw a spanning tree of G.

(b) Use your spanning tree to find a basis for the cycle space of G.

(c) Express the circuits