합성수 모듈로에서 높은 위수의 원소를 결정론적으로 찾기에 관하여

기본 정보

• 논문 ID: 2506.07668
• 제목: On Deterministically Finding an Element of High Order Modulo a Composite
• 저자: Ziv Oznovich, Ben Lee Volk (Efi Arazi School of Computer Science, Reichman University, Israel)
• 분류: cs.DS (데이터 구조 및 알고리즘), math.NT (정수론)
• 제출 시간: 2025년 6월 11일 (arXiv v3)
• 논문 링크: https://arxiv.org/abs/2506.07668

초록

본 논문은 합성수 $N$과 목표 위수 $D \geq N^{1/6}$이 주어졌을 때, $D^{1/2+o(1)}$ 시간 내에 실행되는 결정론적 알고리즘을 제시한다. 이 알고리즘은 곱셈 위수가 최소 $D$ 이상인 원소 $a \in \mathbb{Z}_N^*$를 찾거나 $N$의 비자명 인수를 찾는다. 본 알고리즘은 더 강한 가정 $D \geq N^{2/5}$를 필요로 하는 Hittmeir의 알고리즘을 개선한다. $N$이 $r$제곱 인수($r \geq 2$)를 가질 때, 알고리즘은 $D \geq N^{1/6r}$ 가정 하에서 동일한 보장을 제공한다.

연구 배경 및 동기

문제 배경

1. 정수 인수분해의 도전: 정수 인수분해는 계산 정수론의 핵심 문제이다. 현재 최고의 확률 알고리즘(예: 수체 체)은 준지수 복잡도를 가지며, 최고의 결정론적 알고리즘은 최근까지 강지수 복잡도를 가진다.
2. 결정론적 알고리즘의 중요성: 이론적으로 모든 확률 알고리즘이 다항식 느려짐으로 결정론적 알고리즘에 의해 시뮬레이션될 수 있지만, 무조건부 비확률화 결과를 얻는 것은 복잡성 이론과 알고리즘 설계에서 여전히 중요한 의미를 가진다.
3. 높은 위수 원소의 역할: Hittmeir과 Harvey의 획기적인 작업은 큰 곱셈 위수를 가진 원소를 결정론적으로 찾는 것이 효율적인 결정론적 분해 알고리즘 설계의 핵심임을 보여주었다.

연구 동기

1. 매개변수 범위 개선: Hittmeir의 알고리즘은 $D \geq N^{2/5}$를 요구하며, 이 조건은 상대적으로 엄격하여 알고리즘의 적용 범위를 제한한다.
2. 분해 알고리즘 향상: Harvey-Hittmeir 분해 알고리즘에서 높은 위수 원소를 찾는 단계의 실행 시간이 $N^{1/5+o(1)}$이며, 이는 알고리즘의 병목 중 하나이다.
3. 이론적 의의: 비확률화는 이론 컴퓨터 과학의 중요한 문제이며, 정수론 알고리즘에서 비확률화를 실현하는 것은 깊은 이론적 의의를 가진다.

핵심 기여

1. 매개변수 개선: 목표 위수의 요구사항을 $D \geq N^{2/5}$에서 $D \geq N^{1/6}$으로 감소시켜 알고리즘의 적용 범위를 크게 확장했다.
2. 실행 시간 유지: 매개변수 요구사항을 완화하면서 $D^{1/2+o(1)}$의 실행 시간 복잡도를 유지했다.
3. $r$제곱 경우의 최적화: $N$이 $r$제곱 인수를 가질 때, 요구사항을 $D \geq N^{1/6r}$으로 추가 감소시켰다.
4. 분해 알고리즘 개선: 새로운 분해 부분 프로그램을 제공하여 알려진 잉여류 정보 하에서의 인수분해 방법을 개선했다.
5. 이론적 도구: 연속 정수 중 특정 합동 조건을 만족하는 원소 개수의 더 타이트한 경계를 증명했다.

방법 상세 설명

작업 정의

입력: 합성수 $N$과 목표 위수 $D \geq N^{1/6}$출력: $\mathbb{Z}_N^*$에서 곱셈 위수가 최소 $D$ 이상인 원소 $a$, 또는 $N$의 비자명 인수 시간 복잡도: $D^{1/2+o(1)}$

알고리즘 구조

주 알고리즘 구조 (Algorithm 4.1)

알고리즘은 반복 탐색 전략을 채택하며, 주요 단계는 다음과 같다:

1. 전처리: Strassen 방법을 사용하여 작은 인수 확인
2. 반복 탐색: $a = 2, 3, 4, \ldots$에 대해 탐색
3. 위수 계산: 개선된 Baby-step Giant-step 방법 사용
4. 정보 축적: 검사된 원소 위수의 최소공배수를 기록하는 변수 $M$ 유지
5. 최종 분해: $M$이 충분히 클 때 새로운 분해 알고리즘 사용

핵심 기술 개선

1. 연속 근의 경계 개선 (Claim 2.6)

큰 정수 N, ℓ에 대해, N이 소인수 p > 2ℓ를 가지면,
m = 10√ℓ개의 연속 정수 {a, a+1, ..., a+m} 중에
b^ℓ ≢ 1 (mod N)을 만족하는 원소 b가 존재한다.

이는 Hittmeir 알고리즘의 $O(M)$ 탐색 복잡도를 $O(\sqrt{M})$으로 개선한다.

2. 잉여류 분해 알고리즘 (Theorem 3.2)$N$과 $s \geq N^α$($α \leq 1/(4r)$, $\gcd(N,s) = 1$)이 주어졌을 때, 알고리즘은 $N^{1/(4r)-α+o(1)}$ 시간 내에 $p \equiv 1 \pmod{s}$를 만족하는 모든 $r$제곱 인수를 찾을 수 있다.

기술 혁신점

1. 다항식 구성의 개선

Harvey-Hittmeir 알고리즘을 기반으로, 기본 다항식을 $f(x) = x + P$에서 다음으로 개선했다: $g(x) = x + s' + s'(P - \tilde{P})$ 여기서 $s'$은 $s$의 모듈로 $N$ 역원이고, $\tilde{P}$는 $P$의 모듈로 $s$ 나머지이다.

2. 탐색 공간의 축소

소인수 $p \equiv 1 \pmod{s}$의 정보를 활용하여 근을 찾는 크기를 $H$에서 약 $H/s$로 축소하여, 탐색 구간 개수를 $s$배 감소시킨다.

3. LLL 격 기저 축소의 적용

다항식 시스템을 구성한다: