Fiege Fiat Shamir Question sur les résidus quadratiques

Question

J'étudie actuellement Fiege-Fiat Shamir et suis coincé sur des résidus quadratiques. Je comprends le concept, mais je pense que je ne suis pas sûr de savoir comment les calculer par exemple comment pourrais-je calculer

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 

Je ne comprends pas comment la colonne x =? est calculé. Quelqu'un peut-il m'aider peut-être expliquer la méthode?

Answer 1

La colonne de droite affiche les entiers positifs inférieurs à 21 (le module) dont le résidu quadratique est égal aux valeurs de la colonne de gauche. Ainsi, par exemple, les entiers 1, 8, 13 et 20 ont tous un résidu quadratique égal à 1 modulo 21. Cela signifie que leurs carrés sont congrus à 1 modulo 21. Par exemple,

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

où je me sers =. pour représenter congruence modulo 21. De même,

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

et

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

trouver ces numéros est appelé à trouver des racines carrées mod n. Vous pouvez les trouver en utilisant le Chinese Remainder Theorem (en supposant que vous pouvez factoriser le module).