Algorithms and Complexity
£20-250 GBP
Pagado a la entrega
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; specically, 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 satised.)
(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 veried
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, innite 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 conguration is dened 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
Nº del proyecto: #4459736