7. It is well known that banking transaction require authentication. Every authe

Question

7. It is well known that banking transaction require authentication. Every authentication requires some computations. Suppose it is observed that for these computations, the required time grows as the square of the size of the number Currently, the 32 bit computations take 5 ms time for authentication. The computers are expected to authenticate in no more than 100 ms. What is the largest sized numbers that can be processed to support strong authentication? 8. Some prime numbers appear with a difference of 2. For instance (5, 7) and (11, 13) are such pairs. Find a smallest such pair which is greater than 150 9. In cryptography RSA requires computation of the form a raised to the power of b modulo m. Suppose we have an integer 5. What is the value of 5 raised to the power of 238 modulo 31 (Hint: 5 raised to the power is 1 modulo 31)

Explanation / Answer

1. Here given that for 32 bit computation it takes 2^5 ms (since given time takes is square of n)

32 2^5

64 2^6

128 2^7

But it is required that time should not be more than 100 ms ,therefore the max size can be 64bits.

2. The numbers satisfying the above statement are called as twin primes. i.e. difference between two prime numbers is always 2. When we observe such pairs all of them except (3,5) are of the form (6n ? 1, 6n + 1) i.e both the twin primes will be multiple of 6. Now, when moving to the question prime numbers greater than 150 are : 151, 179, 181, 191, 193, 197. Among them only 191 and 193 are twin primes. Therefore these are smallest pair grater than 150.

3. 5^238 % 31 (given 5^1 % 31 =5)

STEPS:

i) convert 238 to decimal :11101110

start from the right and let k =0 ,1 for each digit (eg :1110 --0 is in 2^0 place 1 is in 2^1 ,next 1 in 2^2 and son on)If the digit is 1 then that part of 2^k is required else not needed.

238=(2^7+2^6+2^5+2^3+2^2+2^1) =2^(7+6+5+3+2+1)

5^238=(5^7+5^6+5^5+5^3+5^2+5^1)

ii) Calcualte for each power of 5 :

5^1 % 31 =5(a%b =a ,if a <b)

5^2=25%31=25

5^3=125%31=1

5^5%31=25

similarly calculate for 5^6,5^7

therefore 5^7+5^6+5^5+5^3+5^2+5^1 = 5*25*25*1*1*5 =15625

finally,15625%31=1

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.