# Algorithms and Complexity

Can send word file as they might not appear clear here. answers will be checked with tutor.

1. A and B want to exchange encrypted messages; speci cally, B wants to send a message M

written in binary format to A, which needs to be encrypted. They agree in using the RSA

Encryption Scheme. Therefore, A sends to B its public key (N; k) = (91; 5).

(a) Why is (N; k) = (91; 5) a valid public key?

(Show that both conditions are satis ed.)

(3 marks)

(b) B's binary message is M = 110.

What decimal number does it represent?

(2 mark)

(c) What is the decimal number representing the encrypted message?

(3 marks)

(d) What is the binary representation of the encrypted message?

(2 marks)

(e) For (N; k) = (91; 5), the decimal number N = 91 has the binary representation 91 =

1  26 + 1  24 + 1  23 + 1  21 + 1  20 = 64 + 16 + 8 + 2 + 1  1011011, i.e. the binary

representation length is n = 7 and the conditions requested in 1(a) can be veri ed

without the use of a computer/calculator. Nevertheless, by today's state of algorithmic

knowledge, RSA encryption is considered to be safe. Why is this the case?

(3 marks)

2. We assume the elementary deterministic model of Turing Machines (L-II: 11 March); in

particular, in nite in both directions tape, tape symbols ? and j, two special states Sstart and

Sstop, and a nite program consisting of instructions [S;X] ! [Y;M; S0].

The initial con guration is de ned by the TM being in state Sstart and the R/W-Head reading

the symbol in the tape-cell left from the leftmost j-symbol, if there is a j-symbol. If there

is no j-symbol as part of the representation of the input, the R/W-Head can be positioned

anywhere on the tape.

We consider TMs processing natural numbers N  0. The numbers are represented by the

corresponding number of j-symbols, e.g. N = 3  j j j and N = 0  empty, i.e., if N = 0 is

the input, then there are only ?-symbols on the tape.

(a) Write a program for a TM that

Beceriler: Algoritma

İşveren Hakkında:
( 1 değerlendirme ) Strood, United Kingdom

Proje NO: #4459736

Calleus