용어 목록 > 이차잉여 (Quadratic Residue)

이차잉여 (Quadratic Residue)

쉽게 풀면

정수를 제곱한 뒤 n으로 나눈 나머지로 나올 수 있는 값을 법 n의 이차잉여라고 합니다. 예를 들어 7로 나눈 나머지 중 제곱수에서 나올 수 있는 값은 1, 2, 4뿐이고 3, 5, 6은 나오지 않습니다. 즉 어떤 합동식이 제곱근을 갖는지를 묻는 개념입니다.

왜 중요한가

정수론에서 이차합동식의 해의 존재 여부를 판정하는 기본 문제이며, 소인수분해 알고리즘과 공개키 암호의 안전성 가정에 직접 연결됩니다. 이차잉여 여부는 쉽게 계산되지만 제곱근 자체를 구하기는 어렵다는 비대칭성이 암호 설계에 활용됩니다.

논문에서는 이렇게 쓰입니다

조금 더 깊게 보면

홀수 소수 p에 대해 0이 아닌 나머지 중 정확히 절반이 이차잉여입니다. 이차잉여 여부를 1과 -1로 표시한 르장드르 기호는 곱셈적 성질을 가져 계산을 쉽게 만들며, 오일러 판정법은 이 값을 지수 (p-1)/2의 거듭제곱 나머지로 계산합니다. 서로 다른 두 홀수 소수 사이의 판정 문제를 맞바꿔 주는 이차상호법칙은 정수론의 대표적 정리로, 계산을 크게 단순화합니다.

주의할 점

이차잉여인지 판정하는 것과 실제 제곱근을 구하는 것은 난이도가 크게 다른 별개의 문제입니다. 또 법이 합성수일 때는 소인수별 결과를 중국인의 나머지 정리로 합쳐야 하며, 르장드르 기호를 그대로 쓸 수 없습니다.

관련 용어