Question

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

The question was posed to me in exam.

Asked question is from Overview in portion Cryptography Overview, TCP/IP and Communication Networks of Cryptograph & Network Security

Answer 1

The correct choice is (a) x≡±16 mod 23

To explain I would say: a=3    3^((23+1)/4)≡3^6≡1    (QR and there is solution)

x ≡ ±3(23 + 1)/4 (mod 23) ≡±16   i.e. x = 7 and 16