Cryptography Multiple Choice Questions on “Number Theory”.
1. Equations have either no solution or exactly three incongruent solutions
a) True
b) False
Answer: b
Clarification: Equations has either no solution or exactly two incongruent solutions.
2. Find the solution of x2≡ 3 mod 11
a) x ≡ -9 mod 11 and x≡ 9 mod 11
b) x ≡ 9 mod 11
c) No Solution
d) x ≡ 5 mod 11 and x ≡ 6 mod 11
Answer: d
Clarification: On finding the quadratic congruencies we get x ≡ 5 mod 11 and x ≡ -5 mod 11.
3. Find the solution of x2≡ 2 mod 11
a) No Solution
b) x ≡ 9 mod 11
c) x ≡ 4 mod 11
d) x ≡ 4 mod 11 and x ≡ 7 mod 11
Answer: a
Clarification: There is no solution possible on solving the congruency.
4. Find the set of quadratic residues in the set –
Z11* = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
a) QR set = {1, 2, 4, 5, 9} of Z11*
b) QR set = {1, 3, 6, 5, 9} of Z11*
c) QR set = {1, 3, 4, 9,10} of Z11*
d) QR set = {1, 3, 4, 5, 9} of Z11*
Answer: d
Clarification: QR set = {1, 3, 4, 5, 9} of Z11* is the set of quadratic residues. The values which have solutions fall under the QR set.
5. In Zp* with (p-1) elements exactly:
(p – 1)/2 elements are QR and
(p – 1)/2 elements are QNR.
a) True
b) False
Answer: a
Clarification: The statement is true concerning elements of Zp* with (p-1) elements.
6. Find the set of quadratic residues in the set –
Z13* = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12}
a) QR { 1, 2, 4,5, 10, 12}
b) QR { 2, 4, 5, 9, 11, 12}
c) QR { 1, 2, 4,5,10, 11}
d) QR { 1, 3, 4, 9, 10, 12}
Answer: d
Clarification: QR { 1, 3, 4, 9, 10, 12}of Z13* is the set of quadratic residues. The values which have solutions fall under the QR set.
7. Euler’s Criterion can find the solution to x2 ≡ a (mod n).
a) True
b) False
Answer: b
Clarification: Euler’s Criterion cannot find the solution to x2 ≡ a (mod n).
8. Find the solution of x2≡ 15 mod 23 has a solution.
a) True
b) False
Answer: b
Clarification: a=15 (15)((23-1)/2)≡(15)11≡-1 (QNR and no solution).
9. Find the solution of x2≡ 16 mod 23
a) x = 6 and 17
b) x = 4 and 19
c) x = 11 and 12
d) x = 7 and 16
Answer: b
Clarification: a=16 (16)((23+1)/4) ≡ (16)6≡1 (QR and there is solution).
x ≡ ±16(23 + 1)/4 (mod 23) ≡±4 i.e. x = 4 and 19.
10. Find the solution of x^2≡3 mod 23
a) x≡±16 mod 23
b) x≡±13 mod 23
c) x≡±22 mod 23
d) x≡±7 mod 23
Answer: a
Clarification: a=3 3((23+1)/4)≡36≡1 (QR and there is solution).
x ≡ ±3(23 + 1)/4 (mod 23) ≡±16 i.e. x = 7 and 16.
11. Find the solution of x2≡ 2 mod 11 has a solution.
a) True
b) False
Answer: b
Clarification: 2 is a QNR.
12. Find the solution of x2≡7 mod 19
a) x≡±16 mod 23
b) x≡±11 mod 23
c) x≡±14 mod 23
d) x≡±7 mod 23
Answer: b
Clarification: a=7 7((19+1)/4)≡75≡1 (QR and there is solution)
x ≡ ±7(19 + 1)/4 (mod 19) ≡±11 i.e. x = 11 and 12.
13. If we use exponentiation to encrypt/decrypt, the adversary can use logarithm to attack and this method is very efficient.
a) True
b) False
Answer: b
Clarification: The first part of the statement is true. But this method is very inefficient as it uses the exhaustive search method.