Unconditional Primality Certificates for the Hexagonal 3-smooth Family p = 3m(m+1) + 1: Deterministic Pocklington Witnesses and Arithmetic Filters

기술 요약: 육각형 3-smooth 가계에 대한 무조건적 원시 증명(Unconditional Primal Certificates)

문제 정의
본 논문은 $m = 2^a 3^b - 1$ ($a, b \ge 1$인 정수)에 대하여 $p = 3m(m + 1) + 1$로 정의되는 중심 육각형 수(centered hexagonal numbers)의 특정 매개변수 하위 가계에 대한 무조건적 소수성 증명 문제를 다룬다. Pocklington–Lehmer 기준은 $p-1$의 완전히 인수분해된 약수 $F > \sqrt{p}$를 제시함으로써 일반적인 거대 정수의 소수성을 증명하는 실용적인 경로를 제공하지만, 각 소인수 $q$에 대한 적절한 "증인"(witnesses, 기저 $w_q$)을 찾는 것이 과제이다. 이 특정 가계의 경우, 약수 $F = 2^a 3^{b+1}$은 완전히 인수분해되어 있으며 무조건적으로 $F > \sqrt{p}$를 만족한다. 그러나 고정된 증인들(구체적으로 $w_2=5$와 $w_3=7$)의 유효성은 기존에 경험적으로 관찰되었으나 엄밀하고 결정론적인 특성화가 결여되어 있었다. 본 논문은 이러한 고정된 증인들이 보편적인지, 그렇지 않다면 그 유효성에 대한 정확한 조건을 제공하는 것을 목표로 한다.

방법론
저자들은 대수적 수론과 기초 산술 시브(sieving)의 결합을 활용한다:

1. Pocklington–Lehmer 프레임워크: 증명은 $p$가 소수이기 위한 조건으로 $w_q^{(p-1)/q} \not\equiv 1 \pmod p$ 및 $\gcd(w_q^{(p-1)/q}-1, p) = 1$을 만족하는 증인 $w_2, w_3$가 존재해야 한다는 기준에 의존한다. $p \equiv 1 \pmod 6$이므로, 이는 $w_2$가 이차 비잉여(quadratic non-residue)이고 $w_3$가 삼차 비잉여(cubic non-residue)임을 확인하는 문제로 귀결된다.
2. 이차 상호 법칙(Quadratic Reciprocity): $w_2 = 5$의 유효성은 레장드르 기호 $\left(\frac{5}{p}\right)$를 사용하여 분석되며, 이는 $m = 2^a 3^b - 1$의 성질을 통해 매개변수 $a$와 $b$와 연관된다.
3. 아이젠슈타인 정수에서의 삼차 상호 법칙(Cubic Reciprocity in Eisenstein Integers): $w_3 = 7$의 유효성은 $\mathbb{Z}[\omega]$ ($\omega = e^{2\pi i/3}$)에서의 삼차 잉여 기호를 사용하여 분석된다. 저자들은 $p = (m+1)^3 - m^3 = \pi \bar{\pi}$라는 명시적 인수분해를 활용하여 아이젠슈타인의 삼차 상호 법칙을 적용한다. 이를 통해 $p$에 대한 7의 삼차 잉여성을 $m \pmod 7$에 대한 조건으로 환원할 수 있다.
4. 산술 필터(Arithmetic Filters): 비용이 많이 드는 거대 수 산술을 수행하기 전에 후보들을 제거하기 위해 세 가지 기초 필터를 도출한다:
   • 모듈로 6 항등식 (자동 적용).
   • $(-3)$ 이차 잉여 시브 (소수 $q \equiv 2 \pmod 3$를 제거).
   • $(a \pmod 3, b \pmod 6)$의 잔여 클래스에 기반한 모듈로 7 금지 클래스 테스트.

주요 기여
본 논문은 경험적 가정을 엄밀한 결정론적 규칙으로 대체하는 두 가지 엄밀한 정리를 제공한다:

• 정리 4.1 (증인 $w_2=5$): 기저 5는 $a - b \equiv 1, 2 \pmod 4$일 때만 유효한 Pocklington 증인이다. 이 조건이 실패하면 5는 이차 잉여이며, 다른 증인을 선택해야 한다.
• 정리 4.5 (증인 $w_3=7$): 기저 7은 $m \not\equiv 2 \pmod 7$일 때만 유효한 Pocklington 증인이다. 이 조건은 $(a \pmod 3, b \pmod 6) \notin \{(0, 1), (1, 5), (2, 3)\}$과 동치이다.
• 결정론적 선택 규칙: 코롤러리 4.9는 이러한 결과들을 종합하여 증인 선택을 위한 완전한 알고리즘을 구성한다. 고정된 증인들이 합동 검사를 통과하지 못할 경우, 알고리즘은 최소의 이차 또는 삼차 비잉여를 결정론적으로 선택하여, 증명 과정이 우연에 의존하지 않고 확실하게 올바름을 보장한다.
• 일반화: 명제 4.7은 7의 삼차 성질에 대한 분석을 더 넓은 범위의 $p = 3m^2 + 3m + 1$ 가계(3-smooth 제약 없음)로 확장하여, $m \pmod{21}$에 기반한 삼차 잉여성을 규명한다.

결과

• 필터 효율성: 모듈로 7 필터와 $(-3)$ 시브의 결합은 거대 수 산술(Miller–Rabin 또는 Pocklington 검증)을 수행하기 전에 후보 쌍 $(a, b)$의 약 87%를 제거한다.
• 계산적 시연: 멀티 코어 구현체("PrimeQuest")를 통해 소비자용 하드웨어에서 4개의 무조건적 소수 증명서를 생성했다. 가장 큰 증명서는 29,998 자릿수의 십진수($m = 2^{19435}3^{19173} - 1$)에 해당하는 소수에 대응한다.
• 검증: 29,998자리의 소수는 독립적으로 재검증되었다. 해당 증명서는 $w_2=5$와 $w_3=7$에 대해 Pocklington 조건을 만족하며, 여유분(margin) $2 \log_2 F - \log_2 p \approx 1.58$ 비트는 무조건적 소수성을 확증한다.

의의 및 범위
본 논문은 자신의 기여를 기록 경신보다는 구조적이고 명시적인 것으로 명확히 규정한다.

• 경험적 가설의 해결: 본 논문은 "5와 7이 항상 작동하는가"라는 이 가계에 대한 미결 질문을 해결하며, 5와 7이 항상 작동하는 것은 아님을 증명하고, 이러한 불확실성을 정확한 합동 조건으로 대체한다.
• 겸손한 주장: 저자들은 본 논문이 "고전적인 미해결 문제를 해결하지 않는다"고 밝힌다. 29,998자리의 소수는 일반적인 기준에서 기록적인 수치는 아니다(일반 목적의 ECPP는 훨씬 더 큰 수를 처리함). 이는 범용적인 프레임워크의 효율성을 일반 컴퓨터 하드웨어에서 입증하는 역할을 한다.
• 인식론적 상태: 모든 이론적 주장(정리 4.1, 4.5, 4.7 및 필터)은 엄밀하며 무조건적이다. 계산 결과는 정밀 산술에 의해 검증되었다. 본 연구는 분석적 이론의 후속 작업으로서, Pocklington 방법이 완전히 결정론적이고 최소화될 수 있는 특정 3-smooth 하위 가계를 분리하여 제시한다.