디오판토스 방정식 (Diophantine Equation)
쉽게 풀면
보통 방정식은 x=1.5, y=2.7처럼 소수나 분수로 된 답도 정답으로 받아들입니다. 하지만 디오판토스 방정식은 "사과 x개와 배 y개를 합쳐 정확히 10개를 산다"처럼, 애초에 반쪽짜리 답이 의미가 없는 상황을 다룹니다. 그래서 정수 해만을 찾도록 조건을 건 방정식입니다. 가장 유명한 예가 페르마의 마지막 정리(x^n+y^n=z^n)이며, 암호학에서 두 정수의 관계를 이용해 열쇠를 만드는 것도 이 방정식의 아이디어에 뿌리를 두고 있습니다.
왜 중요한가
디오판토스 방정식은 정수론의 가장 오래된 연구 대상 중 하나이면서도, 정수 해만 존재해야 하는 실제 응용 문제(암호 키 생성, 격자 문제, 정수 계획법 등)를 수학적으로 정식화하는 자연스러운 틀을 제공하기 때문에 순수수학과 응용수학 양쪽에서 두루 다뤄집니다. 특히 일부 디오판토스 방정식은 정수해를 찾는 것이 계산적으로 매우 어렵다는 성질이 있어, 이 어려움 자체가 암호학에서 안전성의 근거로 활용됩니다.
핵심 정리
디오판토스 방정식은 정수 계수의 다항 방정식이면서 해로는 정수(문제에 따라 자연수)만 관심을 두는 방정식입니다. ‘정수 해만 인정한다’는 조건은 방정식의 모양이 아니라 해에 거는 조건이므로, 같은 식 2x + 3y = 5도 실수 해를 구하면 직선 전체가 답이고 정수 해를 구하면 격자점만 답입니다.
- 일차식
ax + by = c: 정수 해가 있을 필요충분조건은 c가 a와 b의 최대공약수 d의 배수라는 것입니다. 해가 하나 (x₀, y₀) 있으면 나머지 해는 (x₀ + k·b/d, y₀ − k·a/d)(k는 임의의 정수) 꼴이며, 이 해는 유클리드 호제법으로 구합니다. - 고차식:
xⁿ + yⁿ = zⁿ은 n = 2이면 해가 무수히 많지만(피타고라스 세 쌍) n ≥ 3이면 양의 정수 해가 없다는 것이 페르마의 마지막 정리이며, Wiles(1995)가 증명했습니다. - 일반론: 힐베르트의 열 번째 문제는 임의의 디오판토스 방정식이 정수 해를 가지는지 판정하는 일반 알고리즘을 요구했고, 1970년 마티야세비치가 그런 알고리즘이 존재할 수 없음을 보였습니다(Davis, 1973).
예시로 보기
일차식으로 직접 확인(계산). 12x + 18y = 30에서 gcd(12, 18) = 6이고 6은 30을 나누므로 해가 있습니다. 6으로 나누면 2x + 3y = 5이고, (x, y) = (1, 1)이 한 해입니다. 일반해는 x = 1 + 3k, y = 1 − 2k입니다.
| k | x | y | 12x + 18y |
|---|---|---|---|
| −2 | −5 | 5 | 30 |
| −1 | −2 | 3 | 30 |
| 0 | 1 | 1 | 30 |
| 1 | 4 | −1 | 30 |
| 2 | 7 | −3 | 30 |
정수 해는 무수히 많지만 x, y가 모두 양수여야 한다면 1 + 3k > 0과 1 − 2k > 0을 함께 만족하는 정수 k는 0뿐이므로 (1, 1) 하나만 남습니다. 반대로 6x + 9y = 10은 gcd가 3인데 3이 10을 나누지 않으므로 정수 해가 없습니다. 사과와 배를 정수 개로 사는 문제에서 조건(음수 불가, 합계 고정)을 더하면 해의 개수가 이렇게 줄어듭니다.
자주 하는 오해
- “정수 해만 찾는다면 전수 조사로 충분하다.” 해의 범위가 알려져 있지 않으면 어디까지 찾아야 할지 알 수 없습니다. 일반 판정이 불가능하다는 결과(Davis, 1973 소개)는 바로 이 점을 정리한 것입니다.
- “어려운 정수 문제는 곧 암호의 근거다.” Manders와 Adleman(1978)이 두 변수 이차식에 관한 결정 문제들이 NP-완전임을 보인 것처럼, 일부 디오판토스 문제는 계산상 어렵다고 알려져 있습니다. 그러나 어느 방정식이 어렵다는 사실이 곧 특정 암호 방식의 안전성을 보장하지는 않으며, 안전성은 방식별로 따로 논증해야 합니다.
- “일차식이니 해는 하나다.” 위 계산처럼 일차식도 해가 있다면 규칙적으로 무수히 많고, 조건(양수, 범위)으로 개수가 정해집니다.
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 암호 알고리즘의 안전성을 수학적으로 풀기 힘든 정수 방정식 문제에 의존하도록 설계했다는 뜻입니다. 암호학, 정수론, 조합최적화 논문에서 정수 제약이 있는 문제를 정식화할 때 자주 인용됩니다.
조합최적화·운용과학 분야에서는 물품이나 인력처럼 쪼갤 수 없는 자원을 다루는 문제를 디오판토스 방정식 형태로 정식화해 정수해만을 탐색하는 방법론이 자주 사용됩니다.
대수적 정수론 분야에서는 타원곡선이나 대수다양체 위의 정수점을 찾는 문제를 디오판토스 방정식의 해 탐색 문제로 환원해 다루는 경우가 많습니다.
조금 더 깊게 보면
디오판토스 방정식은 미지수와 차수에 따라 난이도가 크게 달라지는데, ax+by=c 같은 선형 방정식은 유클리드 호제법으로 해의 존재 여부와 해 자체를 체계적으로 구할 수 있지만, 페르마의 마지막 정리처럼 고차항이 섞인 방정식은 일반적인 풀이법이 존재하지 않는 경우가 많습니다. 실제로 임의의 디오판토스 방정식에 정수해가 존재하는지를 일반적으로 판정하는 알고리즘은 존재하지 않는다는 사실(힐베르트의 10번째 문제에 대한 부정적 답)이 정수론과 계산가능성 이론을 잇는 중요한 결과로 알려져 있으며, 이러한 계산적 어려움이 일부 암호학적 응용의 이론적 근거가 됩니다.
주의할 점
ax+by=c 형태의 선형 디오판토스 방정식은 c가 a와 b의 최대공약수의 배수일 때만 정수해가 존재하며, 이 최대공약수는 유클리드 호제법으로 구합니다. 해가 존재해도 하나가 아니라 무한히 많은 정수해가 규칙적으로 나열되는 경우가 많다는 점도 혼동하기 쉬운 부분입니다.
헷갈리기 쉬운 용어
‘정수’가 등장하는 비슷한 주제와 구별합니다.
| 용어 | 무엇인가 | 디오판토스 방정식과의 차이 |
|---|---|---|
| 유클리드 호제법 | 나머지 계산의 반복으로 최대공약수를 구하는 알고리즘 | 일차 디오판토스 방정식의 해를 구할 때 쓰는 도구 |
| 최대공약수와 최소공배수 | 두 수의 공약수 중 가장 큰 수와 공배수 중 가장 작은 수 | 일차식의 해 존재 여부를 가르는 판정 기준(gcd가 c를 나누는지) |
| 모듈러 연산 | 나머지를 기준으로 수를 다루는 연산 | ax ≡ c (mod b)는 ax + by = c를 만족하는 정수 y가 있는 것과 같은 말 |
| 연분수 | 수를 분모 안에 분수가 이어지는 꼴로 표현 | 펠 방정식 같은 이차 디오판토스 방정식의 해를 구할 때 쓰이기도 함 |
참고 문헌
- Mordell, L. J. (1969). Diophantine equations. Academic Press.
- Ireland, K., & Rosen, M. (1990). A classical introduction to modern number theory (2nd ed.). Springer-Verlag.
- Davis, M. (1973). Hilbert's tenth problem is unsolvable. The American Mathematical Monthly, 80(3), 233–269.
- Wiles, A. (1995). Modular elliptic curves and Fermat's last theorem. Annals of Mathematics, 141(3).
- Manders, K. L., & Adleman, L. (1978). NP-complete decision problems for binary quadratics. Journal of Computer and System Sciences, 16(2), 168–184.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.