문제

우리는 모듈러 산술에서의 곱셈과 나눗셈을 살펴봤지만, 정수에 대한 모듈러 제곱근을 취하는 것은 무엇을 의미할까요?

아래 문제에서는 p = 29에 대해 작업합니다. 우리는 정수 a = 11을 가져와서 a² = 5 mod 29를 계산할 수 있습니다.

a = 11이므로, a² = 5이고, 우리는 5의 제곱근을 11이라고 말합니다.

이것은 좋은 것처럼 느껴지지만, 이제 18의 제곱근에 대해 생각해 보겠습니다. 위에서 알았듯이, 우리는 a² = 18을 만족하는 어떤 정수 a를 찾아야 합니다.

첫 번째 아이디어는 a = 1부터 시작하여 a = p-1까지 루프를 도는 것입니다. 이 방법에서 p는 너무 크지 않으므로 빠르게 확인할 수 있습니다.

일단 시도해보세요, 이것을 코딩하고 찾아보세요. 제대로 코딩했다면, 모든 a ∈ Fp*에 대해 a² = 18을 만족하는 a를 찾을 수 없을 것입니다.

우리가 보고 있는 것은 F*p의 요소에 대해, 모든 요소가 제곱근을 가지는 것은 아니라는 것입니다. 사실, 우리가 발견한 것은 Fp*의 요소 중 대략 절반에 대해 제곱근이 없다는 것입니다.

정수 x가 존재하는 정수 a로 a² = x mod p를 만족한다면, x는 이차 잔여(Quadratic Residue)라고 말합니다. 그러한 솔루션이 없으면, 정수는 이차 비잔여(Quadratic Non-Residue)입니다.

다른 말로, x는 정수 p에 대한 모듈러 제곱근을 취할 수 있는 경우에 이차 잔여입니다.

아래 목록에서 이차 비잔여 두 개와 이차 잔여 하나가 있습니다.

이차 잔여를 찾고, 그것의 제곱근을 계산하세요. 두 가능한 루트 중에서 더 작은 값을 플래그로 제출하세요.

만약 a² = x이면, (-a)² = x입니다. 그러므로 x가 어떤 유한체에서의 이차 잉여인 경우, 항상 두 가지 해가 있습니다.

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

풀이

a² = x mod p, ints = x

ints 값 중 2차 잉여인 값을 찾고 해당 값이 2차잉여일 때 a 값을 찾으면 된다.

if __name__=="__main__":
    p = 29
    ints = [14, 6, 11]
    # a^2 = x mod p | x = i, a = j | j를 구하는게 목표, ints = 2차잉여
    for i in ints:
        for j in range(p):
            if pow(j, 2, p) == i:
                print(i, j)