기술 요약: 단일 시드 헨젤 리프팅(Single-Seed Hensel Lifting)을 통한 $\mathbb{Z}_{p^e}$ 상의 $X^n - 1$의 명시적 인수분해

1. 문제 정의

본 논문은 $\gcd(n, p) = 1$인 정수 잔여 환(integer residue rings) $\mathbb{Z}_{p^e}$ 상에서의 다항식 $X^n - 1$의 명시적 인수분해를 다룬다. 이 연산은 포스트 양자 암호(특히 ML-KEM 및 ML-DSA와 같은 격자 기반 스킴), 플렛인 슬롯 패킹(plaintext slot packing)이 포함된 완전 동형 암호(FHE), 그리고 대수적 부호 이론(유한 체인 환 위의 순환 부호)에서 매우 중요하다.

$\mathbb{F}_p$ 상에서의 인수분해는 잘 알려져 있으나, 이러한 인수분해를 $\mathbb{Z}_{p^e}$로 리프팅(lifting)하는 과정은 기존 방식에서 심각한 알고리즘적 병목 현상을 야기한다:

• 다항식 헨젤 리프팅(Polynomial Hensel Lifting): $O(n)$ 차수의 전역 코팩터(global cofactor)를 유지하고 업데이트해야 하므로, 각 정밀도 레이어마다 높은 계산 비용이 발생한다.
• 다변량 뉴턴-헨젤 반복법(Multivariate Newton–Hensel Iteration): 각 레이어에서 인수의 계수를 직접 리프팅하려고 시도하지만, $m \times m$ 자코비안 행렬(Jacobian matrix)의 역행렬을 구해야 한다(여기서 $m$은 코셋의 차원이다). $\mathbb{Z}_{p^e}$ 상에서는 영인자(zero-divisors)로 인해 표준 역행렬 계산이 방해받으며, 이는 레이어당 $O(p^{(m-1)^2})$의 지수적 탐색을 강제한다.

SageMath와 같은 현재의 컴퓨터 대수 시스템은 $e > 5$인 경우 이러한 인수분해에 대한 일반적인 지원이 부족하며, 종종 NotImplementedError를 발생시킨다.

2. 방법론

제안된 프레임워크는 전역 차수 $n$을 리프팅 과정에서 분리하고 자코비안 역행렬 계산을 피함으로써 위에서 언급한 병목 현상들을 제거한다.

2.1. 다변량 딕슨 재귀(Multivariate Dickson Recurrence) 및 트레이스 생성

프레임워크는 단일 "시드(seed)" 다항식으로부터 모든 기약 인수의 거듭제곱 합 트레이스(power sum traces)를 생성하기 위해 다변량 딕슨 재귀를 활용한다.

• 시드 발견(Seed Discovery): $\mathbb{F}_p$ 상에서 차수가 $m$인 단일 단항 기약 인수 $G(X)$를 찾는다.
• 트레이스 전파(Trace Propagation): 시드의 계수로 정의된 선형 피드백 시프트 레지스터(LFSR) 구조와 뉴턴-기르드 항등식(Newton–Girard identities)을 사용하여, 전역 트레이스 배열 $\{S_k\}_{k=1}^n$을 생성한다. 이 배열은 $X^n - 1$의 인수분해 중 차원이 $m$인 모든 기약 인수의 계수 정보를 인코딩한다.
• 코셋 디스패치(Coset Dispatch): 순환 코셋(cyclotomic cosets)을 분할하기 위해 다중 등차 차이(Multiple Equal-Difference, MED) 분해가 사용된다. 디스패치 메커니즘은 특정 코셋의 고유 트레이스를 복구하며, 풀 랭크 케이스($m_s = m$)와 퇴화 케이스($m_s < m$) 모두를 모듈러 스케일링을 통해 처리한다.

2.2. 아이디얼 유도 모듈로 원리(Ideal Derivation Modulo Principle)

본 논문은 다항식 아이디얼과 인수분해 좌표를 연결하는 이론적 토대를 구축한다.

• 정리 3 (아이디얼 유도 모듈로 원리): 일반적인 단항 다항식 $G(A, X)$(여기서 계수 $A$는 미지수)에 대해 $X^n - 1$을 다항식 장제법(long division)으로 수행하면, 차수가 $m$ 미만인 나머지 $R(A, X)$를 얻는다. 이 나머지의 계수들은 아이디얼 $I_{n,m}$을 생성한다.
• 의의: 이 아이디얼의 $\mathbb{F}_p$ 상의 근(roots)은 $X^n - 1$의 기약 인수의 계수와 정확히 일치한다. 이는 특정 사례(예: $n=p+1$)에 대한 기존 연구를 임의의 $n$과 $m$으로 일반화한다.

2.3. 코팩터 프리 단일 시드 헨젤 리프팅(Cofactor-Free Single-Seed Hensel Lifting)

$\mathbb{F}_p$ 상의 시드 인수를 $\mathbb{Z}_{p^e}$로 리프팅하기 위해, 프레임워크는 코팩터 프리 헨젤 리프트(정리 4)를 채택한다.

• 메커니즘: 전역 코팩터를 업데이트하거나 자코비안 역행렬을 구하는 대신, 한 번 계산된 $\mathbb{F}_p$ 상의 캐싱된 다항식 역원을 사용하여 단일 시드 인수를 승격시킨다.
• 효율성: 이를 통해 레이어당 리프팅 비용을 전역 차수 $n$ 및 정밀도 깊이 $e$와 무관하게 $O(m^2)$ 대수 연산으로 줄인다.

2.4. 이중 트랙 계수 재구성(Dual-Track Coefficient Reconstruction)

트레이스가 디스패치되면, 프레임워크는 이중 트랙 전략을 사용하여 나머지 인수의 계수를 재구성한다.

1. 기본 트랙 ($p > m$): $k \le m$인 모든 $k$에 대해 $\mathbb{Z}_{p^e}$에서 가역적이므로, 명시적 역행렬 계산을 위해 뉴턴-기르드 항등식을 사용한다.
2. 폴백 트랙 ($p \le m$): $p$가 $k$를 나누는 경우 뉴턴-기르드 역행렬 계산이 실패한다. 프레임워크는 $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$에서 근을 표현하고 계수 행렬의 좌측 영공간(left null space)에 대해 다항식을 구하는 몫환 가우스 소거법(quotient-ring Gaussian elimination)으로 전환한다. 프로베니우스 엔도모피즘(Frobenius endomorphism)은 솔루션의 존재를 보장한다.

3. 주요 기여

1. 아이디얼 유도 모듈로 원리: 모듈러 나머지 추출을 통해 유도된 다변량 딕슨 다항식 아이디얼의 근으로서 모든 인수의 계수를 규정하는 일반적인 정리를 제시하였다.
2. 코팩터 프리 헨젤 리프트: 캐싱된 역원을 사용하여 단일 시드 인수를 $\mathbb{Z}_{p^e}$로 승격시키는 알고리즘을 개발하여, 전역 코팩터 업데이트나 자코비안 역행렬 계산의 필요성을 제거하였다.
3. 이중 트랙 재구성: 뉴턴-기르드 역행렬 계산과 몫환 가우스 소거법을 결합하여, 모든 특성 영역($p > m$ 및 $p \le m$)에서 트레이스 배열로부터 인수 계수를 복구하는 견고한 메커니즘을 제공하였다.

4. 결과 및 복잡도

본 논문은 이론적 복잡도 경계와 경험적 평가를 모두 제공한다.

• 이론적 복잡도: $\mathbb{Z}_{p^e}$ 상에서 $X^n - 1$을 명시적으로 인수분해하기 위한 총 대수적 복잡도는 $O(n + m^3 \log p + e \cdot m^2)$로 제한된다.
  • $O(n)$ 항은 트레이스 생성을 나타낸다.
  • $O(m^3 \log p)$ 항은 시드 발견을 나타낸다.
  • $O(e \cdot m^2)$ 항은 리프팅 과정을 나타내며, 이는 레이어당 거의 상수 수준이다.
• 경험적 성능:
  • 본 프레임워크는 SageMath의 C 기반 FLINT/Pari 엔진(런타임 오토 시딩 오버헤드 포함) 대비 445배의 속도 향상을 달enc성한다.
  • 저자의 이전 "V1" 스칼라 리프트 방식 대비 33.5배의 속도 향상을 달성하였다.
  • 정밀도 깊이가 $e = 1000$을 초과하는 경우에도 레이어당 거의 일정한 리프팅 비용을 검증하였다.

5. 의의

본 논문은 임의의 $n$과 $e > 5$인 경우 $\mathbb{Z}_{p^e}$ 상에서 $X^n - 1$을 인수분해하는 일반 목적의 도구가 부족한 현재의 컴퓨터 대수 시스템의 공백을 메운다고 주장한다. 전역 자코비안 역행렬과 관련된 지수적 장벽과 전역 차수 $n$에 대한 선형 의존성을 제거함으로써, 본 프레임워크는 다음을 가능하게 한다:

• 파라미터 탐색: 임의의 정밀도 깊이에서 FHE 스킴의 슬롯 패킹 파라미터를 효율적으로 탐색할 수 있다.
• 고급 암호 구조: 합성 모듈러스 $q = p^e$ 또는 일반적인 순환 차수 $n$을 사용하는 격자 스킴을 지원하여, 현재 NIST 표준의 제약인 소수 및 2의 거듭제곱 모듈러를 넘어 확장할 수 있다.
• 부호 이론: 현대 통신 시스템에서 필수적인 위상 변조(PSK)를 사용하는 유한 체인 환 상의 순환 부호 및 아이뎀포턴트 생성자(idempotent generators)의 효율적인 구축을 지원한다.

이 연구는 $X^n - 1$의 인수분해를 단순한 이론적 연습이 아니라, 클래식 리프팅 방식의 "심각한 성능 벽"을 극복하여 차세대 암호 및 부호 응용 분야를 실질적으로 가능하게 하는 도구로 자리매김한다.