Cryptography Multiple Choice Questions on “Number Theory”.
1. ᶲ(231)=
a) 230
b) 60
c) 80
d) 120
Answer: d
Clarification: ᶲ(231) = ᶲ(3) x ᶲ(7) x ᶲ(11) = 2 x 6 x 10 = 120.
2. n is prime if and only if n divides (2n – 2).
a) True
b) False
Answer: b
Clarification: This isn’t true for all cases. Take for example 341 which is non prime.
3. Find x for the CRT when x= 2 mod 3; x= 3 mod 5; x = 2 mod 7
a) 33
b) 22
c) 23
d) 31
Answer: c
Clarification: We have M = 3 x 5 x 7 = 105; M/3 = 35; M/5 = 21; M/7 = 15.
The set of linear congruences
35 x b1 = 1 (mod 3); 21 x b2 = 1 (mod 5); 15 x b3 = 1 (mod 7)
has the solutions b1 = 2; b2 = 1; b3 = 1. Then,
x = 2 x 2 c 35 + 3 x 1 x 21 + 2 x 1 x 15 = 233 (mod 105) = 23.
4. Consider a function: f(n) = number of elements in the set {a: 0 <= a < n and gcd(a,n) = 1}. What is this function?
a) Primitive
b) Totient
c) Primality
d) All of the mentioned
Answer: b
Clarification: Such a set is known as Totient.
5. The inverse of 49 mod 37 is –
a) 31
b) 23
c) 22
d) 34
Answer: d
Clarification: 49-1 mod 37 = 34.
6. Six teachers begin courses on Monday Tuesday Wednesday Thursday Friday and Saturday, respectively, and announce their intentions of lecturing at intervals of 2,3,4,1,6 and 5 days respectively. Sunday lectures are forbidden. When first will all the teachers feel compelled to omit a lecture? Use CRT.
a) 354
b) 371
c) 432
d) 213
Answer: b
Clarification: Use CRT to get the answer as 371.
7. How many primitive roots are there for 25?
a) 4
b) 5
c) 7
d) 8
Answer: d
Clarification: 2, 3, 8, 12, 13, 17, 22, 23 are the primitive roots of 25.
Given 2 as a primitive root of 29, construct a table of discrete algorithms and solve for x in the following –
8. 17 x2 = 10 ( mod 29 )
a) x = 3, 22 (mod 29)
b) x = 7, 28 (mod 29)
c) x = 2, 27 (mod 29)
d) x = 4, 28 (mod 29)
Answer: c
Clarification: On solving we get x = 2, 27 (mod 29).
9. x – 4x – 16 = 0 (mod 29)
a) x = 6, 24 (mod 29)
b) x = 9, 24 (mod 29)
c) x = 9, 22 (mod 29)
d) x = 6, 22 (mod 29)
View Answer
Answer: b
Clarification: On solving we get x = 9, 24 (mod 29).
10. x7 = 17 (mod 29)
a) x = 8, 9, 12, 13, 15, 24, 28 (mod 29)
b) x = 8, 10, 12, 15, 18, 26, 27 (mod 29)
c) x = 8, 10, 12, 15, 17, 24, 27 (mod 29)
d) x = 8, 9, 13, 15, 17, 24, 28 (mod 29)
Answer: b
Clarification: On solving we get x = 8, 10, 12, 15, 18, 26, 27 (mod 29).
11. The inverse of 37 mod 49 is –
a) 23
b) 12
c) 4
d) 6
Answer: c
Clarification: 37-1 mod 49 = 4.
12. How many primitive roots are there for 19?
a) 4
b) 5
c) 3
d) 6
Answer: d
Clarification: 2, 3, 10, 13, 14, 15 are the primitive roots of 19.