Question

Find the solution of x^2≡7 mod 19

(a) x≡±16 mod 23

(b) x≡±11 mod 23

(c) x≡±14 mod 23

(d) x≡±7 mod 23

This question was posed to me in semester exam.

This interesting question is from Number Theory topic in division More Number Theory of Cryptograph & Network Security

Answer 1

Correct answer is (b) x≡±11 mod 23

To elaborate: a=7    7^((19+1)/4)≡7^5≡1    (QR and there is solution)

x ≡ ±7(19 + 1)/4 (mod 19) ≡±11   i.e. x = 11 and 12.