Question

Find the solution of x^2≡ 16 mod 23

(a) x = 6 and 17

(b) x = 4 and 19

(c) x = 11 and 12

(d) x = 7 and 16

This question was posed to me during an interview.

The query is from Number Theory topic in chapter More Number Theory of Cryptograph & Network Security

Answer 1

The correct choice is (b) x = 4 and 19

To explain: 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.