Fiege Fiat Shamir Вопрос о квадратичных вычетах

Question

Я сейчас изучаю Fiege-Fiat Shamir и застрял на квадратичных остатках. Я понимаю концепцию, я думаю, но я не уверен, как рассчитать их, например, как бы я рассчитал

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

Я не понимаю, как столбец х =? рассчитывается. Может кто-нибудь помочь мне, может быть, объяснить метод?

Answer 1

В правом столбце показаны натуральные числа, меньшие 21 (модуль), у которых квадратичный остаток равен значениям в левом столбце. Так, например, целые числа 1, 8, 13 и 20 имеют квадратичный остаток, равный 1 по модулю 21. Это означает, что их квадраты совпадают с 1 по модулю 21. Например,

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

, где я использую =. для представления конгруэнтности по модулю 21. Аналогичным образом,

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

и

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

Нахождение этих чисел называется нахождением квадратного корня mod n. Вы можете найти их, используя Китайскую теорему остатка (при условии, что вы можете вычислить модуль).