A primality test for $Kp^n+1$ numbers and a generalization of Safe Primes and Sophie Germain Primes

기술 요약: $Kp^n + 1$ 형태의 수에 대한 소수 판별법 및 세이프 프라임(Safe Primes)과 소피 제르맹 소수(Sophie Germain Primes)의 일반화

문제 정의
본 논문은 정수 $N = Kp^n + 1$ (여기서 $p$는 소수이고 $K < p^n$)의 소수 여부를 결정하는 계산적 과제를 다룬다. 페르마의 소수 판별법($a^{N-1} \equiv 1 \pmod N$)은 계산 비용이 저렴하지만, 확률적이며 그 자체만으로는 소수임을 증명하기에 불충분하다. 프로스 정리(Proth's theorem, $N=K2^n+1$의 경우)나 포클링턴 정리(Pocklington's theorem)와 같은 기존의 결정론적 방법들은 흔히 최대공약수(GCD)를 계산하거나 원분 다항식 $\Phi_p$를 포함한 복잡한 조건을 검증해야 한다. 저자는 이러한 요구 사항을 단순화하는 방법을 모색하며, 특히 GCD 계산 없이 단 한 번의 모듈러 거듭제곱(modular exponentiation)에 의존하여 소수임을 입증할 수 있는 테스트를 목표로 하며, 이를 통해 세이프 프라임 및 소피 제르맹 소수의 개념을 확장하고 분석하고자 한다.

방법론
본 논문은 원소의 법(modulo) $N$에 대한 차수(order)와 $Ap+1$ 형태의 정수의 약수 성질에 관한 정수론적 보조정리들을 활용한다.

1. 프로스 정리의 일반화: 저자는 $Ap+1$이$Dp+1$로 나누어지는 성질과$N$에 대한 원소의 차수 및 그 소인수들 사이의 관계에 관한 보조정리들을 증명한다. 이들은 새로운 소수 판별 기준을 도출하는 데 사용된다.
2. 확률적 및 휴리스틱 분석: 새롭게 정의된 소수 군(families)의 분포를 위해, 저자는 하디-리틀우드(Hardy and Littlewood)의 추측 B와 적분 추정치를 사용하여 이들 소수의 밀도를 모델링한다. 이는 특정 구간 내 소수의 실제 개수와 이론적 점근적 추정치를 비교하는 방식으로 이루어진다.
3. 계산적 검증: 저자는 제안된 분포 추정치의 정확성을 테스트하기 위해 다양한 자릿수(작은 수부터 최대 10,000자리까지)를 가진 소수들에 대해 광범위한 계산을 수행한다.

주요 기여 및 결과

• $Kp^n + 1$에 대한 단순화된 소수 판별법:

  • 정리 2.3: $N = Kp^n + 1$ ($p^n \ge K$인 경우)에 대한 소수 판별법을 제공하며, 이는 오직 두 가지 조건만을 요구한다: (i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ 및 (ii) $L^p \equiv 1 \pmod N$. 이는 이전의 일반화된 방식(예: Grau et al., 2015)에서 요구되었던 GCD 계산을 제거한다.
  • 정리 2.5: 매개변수 $j$ ($0 \le j \le n-1$)를 허용하는 추가적인 일반화를 통해, 소수임을 증명할 수 있는 유효한 밑(base) $a$의 범위를 넓힌다.
  • 정리 3.1 및 3.4: 특정 범위의 $j$ 및 $n$ (예: $p^j \ge p^{n-j} \ge (N-1)^{1/3}$)에 대한 추가적인 테스트를 제공한다. 이러한 조건들은 더 큰 $j$ 값을 가질 수 있게 하여, 무작위로 선택된 밑 $a$가 소수 판별 조건을 만족할 확률을 높임으로써 소수 증명의 성공 가능성을 높인다.
  • 따르는 정리(Corollaries): 본 논문은 특정 범위의 $K$와 $p$에 대한 조건을 충족할 때, 페르마 조건 $a^{N-1} \equiv 1 \pmod N$을 검증하는 것만으로 소수임을 인증할 수 있는 특정 무한 정수 군(예: $N = 2Kp^2 + 1$ 및 $N = 2Kp^3 + 1$)을 식별한다.

• 세이프 프라임 및 소피 제르맹 소수의 일반화:

  • 정의 4.1 ($a$-SafePrime): 소수 $N = 2Kp + 1$은$2K < \log_a(2Kp+1)$을 만족할 때$a$-SafePrime이라 정의된다. 이는 $N-1$의 소인수 $p$가 다른 어떤 인수보다도 현저히 크도록 보장하며, 이는 고전적인 세이프 프라임의 특성을 반영한다.
  • $a$-소피 제르맹 소수($a$-SGP)의 정의: 소수 $p$는 $2K < \log_a(2Kp+1)$를 만족하는 적어도 하나의 $K$가 존재하여 $2Kp+1$또한 소수가 될 때$a$-SGP라고 한다.
  • 분포 분석: 저자는 $a$-SafePrime의 개수를 위한 점근 공식($\alpha_1, \alpha_2$)과 주어진 소수가 $a$-SGP일 확률에 대한 추정치($\alpha_3, \alpha_4, \alpha_5$)를 도출한다.
  • 분포에 관한 추측: 10,000자리까지의 소수를 이용한 계산을 바탕으로 저자는 다음과 같이 제안한다.
    • 추측 5.1: 주어진 소수 $p$가 2-소피 제르맹 소수일 확률은 $p \to \infty$일 때 약 0.76으로 수렴한다.
    • 추측 5.2: $a$-SGP에 대한 위 내용의 일반화로, 확률이 $a$에 의존하는 극한값으로 수렴함을 시사한다.

• 경험적 결과:

  • 본 논문은 2-SafePrime 및 2-소피 제르맹 소수의 실제 개수와 제안된 점근적 추정치를 비교하는 표를 제시한다. 결과는 매우 큰 수(100자리에서 10,000자리)에서도 높은 정확도를 보여준다.
  • 저자는 이 발견을 메르센 소수(Mersenne primes)에 적용하여, 처음 30개의 메르센 소수 중 21개가 2-소피 제르맹 소수임을 확인하였으며, 이를 통해 추정치의 유용성을 검증하였다.
  • 현재 알려진 가장 큰 소수($2^{82,589,933}-1$)가 2-소피 제르맹 소수일 확률은 약 0.7637로 추정된다.

의의
본 논문은 GCD 단계를 제거하면서도 엄밀성을 유지함으로써, $Kp^n + 1$ 군에 대한 기존의 소수 판별법보다 계산적으로 더 단순한 대안을 제공한다고 주장한다. 나아가, 세이프 프라임과 소피 제르맹 소수에 대한 일반화된 프레임워크를 도입하고, 매우 큰 정수에 대해서도 견고해 보이는 이들의 분포에 대한 통계적 모델을 제시한다. 저자는 이러한 결과들이 암호학적 목적으로 큰 소수를 생성하고, 특정 구조적 특성을 가진 소수의 분포를 이해하는 데 유용하다고 제안한다. 본 연구는 확립된 정수론(Proth, Pocklington, Hardy-Littlewood)에 기반하며, 이를 새로운 보조정리와 경험적 검증을 통해 확장한다.