연분수 (Continued Fraction)
쉽게 풀면
우리가 흔히 쓰는 소수(3.14159...)나 분수(22/7)는 하나의 수를 한 줄로 표현하는 방법입니다. 연분수는 같은 수를 조금 다르게, "몫을 구하고 나머지의 역수를 취하고, 다시 몫을 구하고 나머지의 역수를 취하는" 과정을 계단처럼 반복해서 표현합니다. 예를 들어 유클리드 호제법으로 두 수의 최대공약수를 구할 때 나오는 몫들을 순서대로 늘어놓으면 그 자체가 연분수가 됩니다. 신기하게도 무리수를 연분수로 표현하면, 소수로 표현할 때보다 훨씬 적은 항만으로도 아주 정확한 유리수 근사값(최선의 근사분수)을 얻을 수 있습니다.
왜 중요한가
연분수는 "가장 적은 항으로 가장 정확한 유리수 근사를 얻는" 방법이라는 점에서, 무리수나 딱 떨어지지 않는 비율을 다뤄야 하는 여러 분야의 공통 도구로 쓰입니다. 정수론에서는 디오판토스 방정식의 정수해나 큰 수의 소인수분해와 관련된 알고리즘의 이론적 기반이 되고, 역학계·신호처리 분야에서는 두 주기 비율을 정수비로 근사해 공진이나 준주기성을 분석하는 데 쓰입니다. 또한 암호학의 일부 공개키 공격 기법도 연분수 근사의 성질에 기대고 있어, 순수수학과 응용 분야 양쪽 논문에서 반복적으로 등장하는 개념입니다.
논문에서는 이렇게 쓰입니다
이 문장은 딱 떨어지지 않는 무리수 비율을 다루기 어려운 상황에서, 연분수 전개를 통해 오차가 가장 작은 유리수 근사값을 구해 계산에 활용했다는 뜻입니다. 정수론뿐 아니라 신호처리, 역학계 연구에서 무리수를 유리수로 근사할 때 등장합니다.
암호학에서는 특정 조건 아래 공개키의 구성 요소들 사이 비율이 연분수로 잘 근사되는 성질을 이용해 취약점을 분석하는 데 연분수 전개가 활용된다는 뜻입니다. 이는 암호 시스템의 안전한 매개변수 선택 기준을 세우는 근거로도 쓰입니다.
기계공학에서는 이론적으로 원하는 회전비가 무리수이거나 매우 복잡한 분수일 때, 실제로 제작 가능한 정수 개수의 톱니를 가진 기어 조합을 찾기 위해 연분수의 근사분수를 활용한다는 의미입니다.
조금 더 깊게 보면
연분수를 특정 항에서 끊어 만든 유리수를 "근사분수(convergent)"라고 하며, 이 근사분수들은 같은 분모 크기 안에서 원래 수에 가장 가깝게 다가가는 최선의 근사라는 성질을 가집니다. 논문에서는 이 성질을 이용해 "몇 번째 근사분수까지 사용했는가"를 정밀도의 기준으로 제시하는 경우가 많습니다. 또한 각 항이 유한한 개수로 끝나면 유리수, 무한히 이어지면 무리수를 나타내며, 특정한 패턴(주기적 반복)이 나타나는 경우는 이차무리수와 관련된 성질로 다뤄지기도 합니다.
주의할 점
연분수는 소수 근사와 달리 "몇 자리까지 정확한가"가 아니라 "몇 번째 항까지 취했는가"로 정밀도를 따집니다. 항을 하나씩 늘릴 때마다 근사 오차가 이전 근사보다 항상 작아진다는 성질이 있으며, 이는 디오판토스 방정식의 정수해를 찾는 데도 활용됩니다.