Fiege Fiat Shamir Question about quadratic residues

Question

Hello people

I am currently studying Fiege-Fiat Shamir and am stuck on quadratic residues. I understand the concept i think but im not sure how to calculate them for example how would i calculate

v   |  x^2 = v mod 21  |   x =?
___________________________________
1     x^2 = 1 mod 21    1, 8, 13, 20
4     x^2 = 4 mod 21    2, 5, 16
7     x^2 = 7 mod 21    7, 14
9     x^2 = 9 mod 21    3, 18
15    x^2 = 15 mod 21   6, 15
16    x^2 = 16 mod 21   4, 10, 11, 17
18    x^2 = 18 mod 21   9, 12

I do not understand how the column x=? is calculated. Can anyone help me maybe explain the method?

Answer 1

The right-hand column shows the positive integers less than 21 (the modulus) that have quadratic residue equal to the values in the left-hand column. So, for example, the integers 1, 8, 13 and 20 all have quadratic residue equal to 1 modulo 21. This means that their squares are congruent to 1 modulo 21. For example,

8 * 8 = 64 = 63 + 1 = 21 * 3 + 1 =. 0 + 1 mod 21 =. 1 mod 21

where I am using =. to represent congruency modulo 21. Similarly,

13 * 13 = 169 = 168 + 1 = 21 * 8 + 1 =. 0 + 1 mod 21 =. 1 mod 21

and

20 * 20 = 400 = 399 + 1 = 21 * 19 + 1 =. 0 + 1 mod 21 =. 1 mod 21.

Finding these numbers is called finding square roots mod n. You can find them using the Chinese Remainder Theorem (assuming that you can factor the modulus).