Quadratic Residues - 제곱 잉여

서론

과연 크립토의 수학은 어디까지 가는가... ㅋㅋㅋ

 

이론

요약하자면

x^2 ≡ a mod n

을 만족하는 정수 x가 있으면 a는 n의 제곱 잉여, 없으면 제곱 비잉여 라고 한다.

 

예를 들어 n =7 이라고 가정하면

1^2 ≡ 1 ≡ 1 mod 7

2^2 ≡ 4 ≡ 4 mod 7

3^2 ≡ 9 ≡ 2 mod 7

4^2 ≡ 16 ≡ 2 mod 7

5^2 ≡ 25 ≡ 4 mod 7

6^2 ≡ 36 ≡ 1 mod 7

... (이후에는 반복됨)

이기 때문에 1,2,4가 7의 제곱 잉여가 된다.

한편, 3,5,6은 비 제곱 잉여가 된다.

 

한번 더 해보자.

만일 n이 13이라면

1^2 ≡ 1 ≡ 1 mod 13

2^2 ≡ 4 ≡ 4 mod 13

3^2 ≡ 9 ≡ 9 mod 13

4^2 ≡ 16 ≡ 3 mod 13

5^2 ≡ 25 ≡ 12 mod 13

6^2 ≡ 36 ≡ 10 mod 13

7^2 ≡ 49 ≡ 10 mod 13

8^2 ≡ 64 ≡ 12 mod 13

9^2 ≡ 82 ≡ 3 mod 13

10^2 ≡ 100 ≡ 9 mod 13

11^2 ≡ 121 ≡ 4 mod 13

12^2 ≡ 144 ≡ 1 mod 13

...(이후에는 반복됨)

이기 때문에 제곱 잉여는 1,3,4,9,10,13이 된다.

 

여기서 a^2 은 (-a)^2 과 같은 값을 가지기에 항상 두개의 a를 가진다.

 

Code

이를 코딩해보자.

더 쉬운 방법이 있을지 모르겠지만... 그냥 1부터 n/2 까지 계산했으며, 홀수 case를 고려해 한번 더 실행해줬다.

n = int(input())
a = []

for i in range(1,1+n//2,1):
    a.append((i**2)%n)

print(a)

 

┌──(kali㉿kali)-[~/Downloads]
└─$ python solve.py
7
[1, 4, 2]
                                                                                                                   
┌──(kali㉿kali)-[~/Downloads]
└─$ python solve.py
11
[1, 4, 9, 5, 3]
                                                                                                                   
┌──(kali㉿kali)-[~/Downloads]
└─$ python solve.py
15
[1, 4, 9, 1, 10, 6, 4]