[CryptoHack] Quadratic Residues (제곱 잉여)

Quadratic Residues는 제곱 잉여 또는 이차 잉여 라고 부른다.

위키에서 다음과 같이 설명한다.

wikipedia

---

 

크립토핵에선 모듈로 p = 29를 예시로 든다.

정수 a = 11을 취하고 a^2 = 5 mod 29를 계산해보자.

a % p = 11, a^2 % p = 5이므로 5의 제곱근은 11이다.

 

이번엔 18의 제곱근을 구해보자.

제곱근을 찾기 위해 a^2 = 18 mod 29를 만족하는 수 a를 찾아야 한다.

하지만 0 ~ 28까지의 수 중에서 만족하는 수가 없다.

 

이렇게 식 a^2 = x mod p 를 만족하는 a가 존재할 때

정수 x는 a에 대한 제곱 잉여라고 할 수 있다.

위키에서 이러한 제곱 잉여는 홀수인 소수 p에 대하여 (p-1)/2 개가 존재한다고 한다.

 

연습 문제는 다음과 같다.

# 아래 목록에는 제곱 비잉여 2개와 제곱 잉여 1개가 있습니다.
# 제곱 잉여를 찾은 다음 제곱근을 계산하여 두 개의 가능한 루트 중 더 작은 것을 플래그로 제출하십시오.
p = 29
ints = [14, 6, 11]

 

0부터 28까지 총 29개로 그렇게 많지 않으므로 전수 조사가 가능하다.

p = 29
ints = [14, 6, 11]

for x in ints:
    for a in range(p):
        if pow(a,2,p) == x:
            print(x,a)
            break

6 8

 

정답은 8이다.

 

---

레퍼런스

https://cryptohack.org/courses/modular/root0/

CryptoHack – Home

https://ko.wikipedia.org/wiki/%EC%A0%9C%EA%B3%B1_%EC%9E%89%EC%97%AC

제곱 잉여 - 위키백과, 우리 모두의 백과사전