On the Inversion Modulo a Power of an Integer

이 논문은 소수 거듭제곱에 대한 역수 계산 알고리즘을 일반 정수 거듭제곱으로 확장하여 컴퓨터 아키텍처의 연산 특성을 활용한 효율적인 알고리즘을 제안하고, 소수 거듭제곱에 대한 기존 역수 계산 방법도 일반 정수 거듭제곱으로 일반화한 결과를 담고 있습니다.

핵심

1. 문제 상황: "나누기"는 너무 비싸다!

컴퓨터 세상에서 숫자를 나눴을 때의 나머지 (Modulo) 를 구하는 것은 매우 중요합니다. 하지만 컴퓨터에게 **'나눗셈 (Division)'**은 **'곱셈 (Multiplication)'**보다 훨씬 느리고 에너지가 많이 드는 고된 일입니다. 마치 무거운 돌을 굴려서 이동시키는 것과 같습니다.

그래서 수학자들은 "나눗셈을 곱셈으로 바꾸면 어떨까?"라고 고민해 왔습니다. 특히, **어떤 수 $a$에 대해 $a \times x = 1$이 되는 수 $x$ (역수)**를 구하는 작업은 암호학 (RSA 등) 의 핵심인데, 이걸 구할 때 나눗셈을 피하는 것이 핵심 과제였습니다.

2. 기존 방법: "특수한 도구를 가진 전문가들"

이전까지의 방법들은 주로 특수한 상황에만 잘 작동했습니다.

• 코치 (Koç) 의 방법: 소수 (Prime number) 의 거듭제곱 (예: $5^3$,$3^4$) 일 때만 아주 잘 작동하는 '정교한 시계공' 같은 방법입니다.
• 허찰라 (Hurchalla) 의 방법: 컴퓨터가 가장 잘 다루는 2 의 거듭제곱 (예: $2^{64}$) 일 때 가장 빠른 '스피드 레이서' 같은 방법입니다.

하지만 문제는 **"그렇다면 10 진법 (10) 이나 60 진법 (60) 처럼 소수가 아닌 숫자를 기준으로 하거나, 2 의 거듭제곱이 아닌 일반적인 수를 다룰 때는 어떡하지?"**였습니다. 기존 방법들은 이 경우엔 너무 느리거나 아예 쓸모가 없었습니다.

3. 이 논문의 해결책: "초등학교 곱셈의 지혜"

저자 (서광우, 천윤효, 양빙신) 는 **"왜 복잡한 공식을 쓰지, 우리가 어릴 때 배운 '초등학교 곱셈 (Schoolbook Multiplication)'을 다시 보자!"**라고 제안합니다.

🏫 비유: 레고 블록으로 탑 쌓기

상상해 보세요. 거대한 탑 (큰 수) 을 쌓으려는데, 바닥에 10이라는 기준이 있습니다.

• 기존 방법: 탑을 쌓을 때마다 무거운 나눗셈 기계를 돌려서 높이를 재고 다듬었습니다.
• 이 논문의 방법: "아! 곱셈을 할 때 생기는 '올림 (Carry)' 숫자를 잘만 활용하면, 나눗셈 없이도 다음 블록을 정확히 끼울 수 있구나!"라고 깨달았습니다.

이들은 **컴퓨터가 가장 잘하는 '덧셈'과 '오른쪽 이동 (Shift)'**만 반복해서 역수를 구하는 알고리즘을 만들었습니다.

• 핵심 아이디어: "나눗셈" 대신 "올림 수를 계산해서 다음 단계로 넘기는" 방식을 썼습니다.
• 장점: 이 방법은 어떤 수 ($n$) 를 기준으로 하든 (10 이든, 64 이든, 128 이든) 유연하게 작동합니다. 마치 어떤 모양의 레고 블록이든 맞춰서 탑을 쌓을 수 있는 만능 키트 같은 것입니다.

4. 실험 결과: "컴퓨터의 본능을 자극하다"

이 논문은 특히 64 비트 컴퓨터와 128 비트 컴퓨터 환경에서 이 방법을 테스트했습니다.

• 결과: 기존의 fastest 방법들보다 훨씬 더 빨랐습니다.
• 이유: 컴퓨터는 64 비트 숫자를 한 번에 처리하는 것이 가장 자연스럽습니다. 이 알고리즘은 컴퓨터의 '본능' (내장 연산) 을 그대로 활용하도록 설계되었기 때문입니다.
• 재미있는 사실: 64 비트 컴퓨터에서 128 비트 단위로 계산을 하면, 오히려 64 비트 단위로 계산할 때보다 더 빨라지기도 했습니다. (마치 큰 화물을 한 번에 실어 나르는 트럭이, 작은 화물을 여러 번 나르는 것보다 효율적인 것과 같습니다.)

5. 두 번째 기여: "허찰라 방법의 확장"

논문 후반부에서는 허찰라 (Hurchalla) 의 유명한 방법을 더 넓은 세상으로 확장했습니다.

• 기존: 오직 2 의 거듭제곱 ($2^s$) 만 가능.
• 확장: **어떤 수 $n$의 거듭제곱 ($n^{2s}$)**에서도 작동하도록 일반화했습니다.
• 방법: 복잡한 미분이나 고급 수학 대신, **단순한 대수학 (Algebra)**의 마법 (식 변형) 만으로 증명했습니다. 이는 마치 "복잡한 기계 없이도 간단한 레버 하나로 무거운 물건을 들 수 있다"는 것을 보여주는 것과 같습니다.

📝 한 줄 요약

이 논문은 **"컴퓨터가 가장 좋아하는 덧셈과 이동 연산만 써서, 어떤 수를 기준으로 하든 역수를 구할 수 있는 초고속 알고리즘"**을 개발했습니다.

이는 마치 무거운 돌 (나눗셈) 을 굴리는 대신, 미끄럼틀 (올림 계산) 을 만들어서 숫자들을 순식간에 목적지로 보내는 것과 같습니다. 암호학, 통신, 그리고 모든 디지털 기술의 속도를 한 단계 업그레이드할 수 있는 중요한 발견입니다.

기술 요약

이 논문은 정수 $n$의 거듭제곱 $n^k$에 대한 모듈로 역수 (modular inverse) $x = a^{-1} \pmod{n^k}$를 계산하는 효율적이고 일반적인 알고리즘을 제안하고, 기존에 제한적이었던 허셀 리프팅 (Hensel lifting) 기반 방법들을 일반화하는 내용을 다루고 있습니다. 주요 내용은 다음과 같습니다.

1. 문제 제기 (Problem)

현대 암호학 (RSA, 타원곡선 암호, 포스트 양자 암호 등) 과 통신 시스템에서는 대규모 정수 연산, 특히 모듈로 역수 계산이 핵심적인 역할을 합니다.

• 기존 한계:
  • Koč 알고리즘: 소수 $p$에 대한 거듭제곱 $p^k$에 대해서는 효율적이지만, 일반적인 정수 $n$ (소수가 아닌 경우) 에 대해서는 적용이 제한적입니다.
  • 허셀 리프팅 (Hensel Lifting) 기반 방법 (Dumas, Hurchalla): 주로 소수 $p$의 제곱 형태인 $p^{2s}$ (특히 $p=2$) 에 최적화되어 있습니다. 일반적인 $n$이나 $n^k$ 형태에는 직접 적용하기 어렵습니다.
  • 나눗셈 비용: 일반적인 역수 계산은 나눗셈을 수반하며, 이는 곱셈에 비해 계산 비용이 높습니다. 특히 $n$이 2 의 거듭제곱이 아닌 경우 (예: 10 진법, 12 진법 등) 나눗셈 최적화가 어렵습니다.

2. 방법론 (Methodology)

이 논문은 크게 두 가지 주요 접근법을 제시합니다.

A. 학교용 곱셈 (Schoolbook Multiplication) 에서 영감을 받은 일반화된 알고리즘

• 동기: $n$진법 (radix-$n$) 곱셈에서의 '올림 (carry)' 연산 구조를 역수 계산에 적용합니다.
• 핵심 아이디어:
  • $ax = 1 + \ell n^k$ 관계를 가정하고, $x$를 $n$진법으로 표현 ($x = X_0 + X_1 n + \dots$) 합니다.
  • 곱셈 과정에서 발생하는 올림 (carry) $q_i$를 재귀적으로 계산하여 각 자릿수 $X_i$를 구합니다.
  • 알고리즘 3.1 (Inversion Modulo a Power):
    • 초기값 $c = a^{-1} \pmod n$을 구합니다.
    • $T_0 = -1$로 설정하고, $T_{i} = T_{i-1} + X_{i-1}a / n$ 및 $X_i = -c T_i \pmod n$ 공식을 반복하여 $k$개의 자릿수를 생성합니다.
    • 이 과정은 덧셈과 $n$으로의 오른쪽 시프트 (나눗셈) 만을 사용하며, 곱셈은 $n$보다 작은 숫자 (자릿수) 와의 곱셈으로 제한됩니다.
• 장점: $n$이 어떤 정수 ($n>1$) 라도 적용 가능합니다. 특히 컴퓨터 아키텍처의 기본 비트 단위 (예: $n=2^{64}, 2^{128}$) 를 활용하여 내장 연산을 최대화할 수 있습니다.

B. 허셀 리프팅 방법의 일반화 (Generalization of Hensel Lifting)

• 기존 방법: Dumas 와 Hurchalla 는 $p^{2s}$ 형태의 모듈러스에 대해 뉴턴 - 라프슨 (Newton-Raphson) 반복을 사용하여 역수를 계산했습니다.
• 일반화 (알고리즘 4.1):
  • 임의의 정수 $n>1$에 대해 $a^{-1} \pmod{n^{2s}}$를 계산할 수 있도록 대수적 조작을 통해 유도했습니다.
  • 초기 근사치 $x_0 = a^{-1} \pmod{n^{2h_0}}$를 구한 후, $y = 1 - ax_0 \pmod{n^{2s}}$를 정의하고 $x_{m+1} = x_m(1 + y^{2^m}) \pmod{n^{2s}}$ 형태의 재귀식을 사용합니다.
  • 이는 분할 정복 (divide-and-conquer) 전략을 기반으로 하며, 기존 Hurchalla 알고리즘을 $n$이 소수가 아닌 경우로 확장한 것입니다.

3. 주요 기여 (Key Contributions)

1. 범용성 (Generality): 소수 거듭제곱 ($p^k$) 에 국한되었던 Koč 알고리즘을 임의의 정수 $n$의 거듭제곱 ($n^k$) 으로 확장했습니다. 이는 10 진법이나 60 진법 등 소수 거듭제곱이 아닌 진법 시스템에서도 역수 계산을 효율적으로 수행할 수 있게 합니다.
2. 효율성 (Efficiency):
   • 알고리즘 3.1 은 $n=2^{64}$ 또는 $n=2^{128}$과 같이 컴퓨터의 네이티브 비트 너비와 일치할 때 최적의 성능을 발휘합니다.
   • Koč 의 이진 버전 알고리즘과 Hurchalla 알고리즘보다 훨씬 적은 연산 횟수와 더 빠른 실행 시간을 보입니다.
3. 이론적 증명: Koč 알고리즘의 정확성에 대한 새로운 증명 (Proposition 2.1) 을 제시했으며, 이를 통해 $a^{-1} \pmod{n^s}$뿐만 아니라 $(n^s)^{-1} \pmod a$도 동시에 얻을 수 있음을 보였습니다.
4. Hensel 리프팅의 확장: $p^{2s}$ 형태에 국한되었던 Hurchalla 알고리즘을 $n^{2s}$ 형태로 일반화하여, 더 넓은 범위의 모듈러스에 적용 가능한 대수적 유도를 제시했습니다.

4. 실험 결과 (Results)

• 실험 환경: Ubuntu 24.04, AMD Ryzen 7 8845HS, GCC 14.2.0.
• 비교 대상: Koč 알고리즘 (이진 버전), Hurchalla 알고리즘.
• 성능:
  • $n=2^{64}$와 $n=2^{128}$을 사용한 제안된 알고리즘 3.1 은 기존 방법들에 비해 압도적인 속도 향상을 보였습니다.
  • 예를 들어, 모듈러스 길이가 4096 비트일 때, Koč 알고리즘은 약 389,627 ns 가 소요된 반면, 제안된 알고리즘 ($n=2^{64}$) 은 약 7,253 ns, ($n=2^{128}$) 은 약 4,989 ns 로, 약 50~80 배 이상 빠릅니다.
  • $n=2^{128}$ 설정이 $n=2^{64}$ 설정보다 더 큰 모듈러스에서 더 효율적인 것으로 나타났습니다.

5. 의의 및 결론 (Significance)

이 논문은 모듈로 역수 계산 분야에서 다음과 같은 중요한 의의를 가집니다:

• 하드웨어 최적화: 현대 컴퓨터 아키텍처 (64 비트 또는 128 비트 워드) 에 맞춰 연산을 최적화함으로써, 암호학 및 수치 계산에서의 연산 오버헤드를 크게 줄였습니다.
• 유연성: 소수 거듭제곱이라는 제약을 벗어남으로써, 다양한 진법 시스템과 임의의 정수 모듈러스를 가진 응용 프로그램에 적용 가능한 강력한 도구를 제공합니다.
• 실용성: 제안된 알고리즘은 구현이 간단하고 (덧셈과 시프트 위주), 기존 곱셈 기반 알고리즘보다 훨씬 빠르므로, 고성능 암호 시스템 및 실시간 통신 프로토콜의 성능 향상에 직접적으로 기여할 수 있습니다.

요약하자면, 이 연구는 학교용 곱셈의 원리를 현대 컴퓨터 아키텍처에 적용하여 임의의 정수 거듭제곱에 대한 역수 계산을 획기적으로 가속화하고, 기존 이론적 방법들을 일반화한 성공적인 사례입니다.