디오판토스 방정식 (Diophantine Equation)
쉽게 풀면
보통 방정식은 x=1.5, y=2.7처럼 소수나 분수로 된 답도 정답으로 받아들입니다. 하지만 디오판토스 방정식은 "사과 x개와 배 y개를 합쳐 정확히 10개를 산다"처럼, 애초에 반쪽짜리 답이 의미가 없는 상황을 다룹니다. 그래서 정수 해만을 찾도록 조건을 건 방정식입니다. 가장 유명한 예가 페르마의 마지막 정리(x^n+y^n=z^n)이며, 암호학에서 두 정수의 관계를 이용해 열쇠를 만드는 것도 이 방정식의 아이디어에 뿌리를 두고 있습니다.
왜 중요한가
디오판토스 방정식은 정수론의 가장 오래된 연구 대상 중 하나이면서도, 정수 해만 존재해야 하는 실제 응용 문제(암호 키 생성, 격자 문제, 정수 계획법 등)를 수학적으로 정식화하는 자연스러운 틀을 제공하기 때문에 순수수학과 응용수학 양쪽에서 두루 다뤄집니다. 특히 일부 디오판토스 방정식은 정수해를 찾는 것이 계산적으로 매우 어렵다는 성질이 있어, 이 어려움 자체가 암호학에서 안전성의 근거로 활용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 암호 알고리즘의 안전성을 수학적으로 풀기 힘든 정수 방정식 문제에 의존하도록 설계했다는 뜻입니다. 암호학, 정수론, 조합최적화 논문에서 정수 제약이 있는 문제를 정식화할 때 자주 인용됩니다.
조합최적화·운용과학 분야에서는 물품이나 인력처럼 쪼갤 수 없는 자원을 다루는 문제를 디오판토스 방정식 형태로 정식화해 정수해만을 탐색하는 방법론이 자주 사용됩니다.
대수적 정수론 분야에서는 타원곡선이나 대수다양체 위의 정수점을 찾는 문제를 디오판토스 방정식의 해 탐색 문제로 환원해 다루는 경우가 많습니다.
조금 더 깊게 보면
디오판토스 방정식은 미지수와 차수에 따라 난이도가 크게 달라지는데, ax+by=c 같은 선형 방정식은 유클리드 호제법으로 해의 존재 여부와 해 자체를 체계적으로 구할 수 있지만, 페르마의 마지막 정리처럼 고차항이 섞인 방정식은 일반적인 풀이법이 존재하지 않는 경우가 많습니다. 실제로 임의의 디오판토스 방정식에 정수해가 존재하는지를 일반적으로 판정하는 알고리즘은 존재하지 않는다는 사실(힐베르트의 10번째 문제에 대한 부정적 답)이 정수론과 계산가능성 이론을 잇는 중요한 결과로 알려져 있으며, 이러한 계산적 어려움이 일부 암호학적 응용의 이론적 근거가 됩니다.
주의할 점
ax+by=c 형태의 선형 디오판토스 방정식은 c가 a와 b의 최대공약수의 배수일 때만 정수해가 존재하며, 이 최대공약수는 유클리드 호제법으로 구합니다. 해가 존재해도 하나가 아니라 무한히 많은 정수해가 규칙적으로 나열되는 경우가 많다는 점도 혼동하기 쉬운 부분입니다.