2 차 잔류 물에 대한 Fiege Fiat Shamir 질문

Question

나는 현재 Fiege-Fiat Shamir를 연구하고 있으며 2 차 잔류 물에 갇혀 있습니다. 나는 내가 생각하는 개념을 이해하지만 예를 들어 어떻게 계산하는지 계산하는 방법을 잘 모르겠습니다.

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

열 x = 어떻게 열이 이해가되지 않습니까? 계산됩니다. 누구든지 방법을 설명 할 수 있습니까?

Answer 1

오른쪽 열은 양의 정수를보다 적게 보여줍니다 21 (모듈러스) 왼쪽 열의 값과 동일한 2 차 잔기를 갖는 (모듈러스). 예를 들어 정수 1, 8, 13 그리고 20 모두 2 차 잔기를 가지고 있습니다 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.

이 숫자를 찾는 것을 찾은 사각형 루트 모드라고합니다 n. 당신은 그들을 사용하여 찾을 수 있습니다 중국의 나머지 정리 (모듈러스를 고려할 수 있다고 가정).