Devam Ediyor

Algorithms and Complexity

Need to answer these questions

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

Daha fazlasını görün: why binary, encryption algorithm, what algorithm, using algorithms, use algorithms, the algorithms, special needs calculator, representing algorithms, program algorithms, number algorithms, message encryption algorithm, key encryption algorithms, deterministic algorithms, deterministic algorithm, con ed, computer complexity, computer algorithms, complexity algorithms, c algorithms, binary algorithms, binary algorithm, algorithms using, algorithms encryption, algorithms computer, algorithms complexity

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

Proje NO: #4459736



Hi, I have experience in Algorithms. Let me help you.

5 gün içinde 99£ GBP
(3 Değerlendirme)