Primorial 매직넘버로 소수 판정 가속하기 - 정직한 탐색기
# Primorial 매직넘버로 소수 판정 가속하기 - 정직한 탐색기
## 시작은 단순한 호기심이었다
큰 소수를 빠르게 판별하는 방법을 연구하다가 이런 생각을 하게 됐다.
> 작은 소수들의 곱(primorial)을 매직넘버로 쓰면 합성수를 빠르게 거를 수 있지 않을까? 그리고 그 매직넘버의 비트 패턴이 특별하면, 나눗셈을 shift 연산으로 대체할 수 있지 않을까?
이 호기심으로 시작한 탐색이 며칠간의 알고리즘 작성, 통계 분석, 벤치마크 측정으로 이어졌다. 결과는 일부는 성공이었고 일부는 솔직히 실패였다. 이 글은 그 과정을 정직하게 정리한 기록이다.
## 1단계: 1016비트 매직넘버 만들기
처음 시도한 것은 단순했다.
```python
# 작은 소수 127개를 곱해서 1016비트 매직넘버 만들기
M = 2 × 3 × 5 × 7 × ... × (127번째 적절한 소수)
```
이 매직넘버 M에 대해 후보 N의 합성수성을 검사하려면:
```python
if gcd(N, M) > 1:
# N은 합성수 (M의 어떤 소인수로 나눠짐)
```
**측정 결과**: 91.42%의 합성수가 한 번의 gcd 연산으로 탈락. 이론적으로 Mertens의 정리가 예측한 값과 정확히 일치했다.
**Mertens 3 정리**:
```
∏(p ≤ x) (1 - 1/p) ~ e^(-γ) / log(x)
```
x = 1000일 때 이 값은 약 0.0858. 즉 약 8.58%만 통과하고 91.42% 탈락. 측정값과 일치.
이 단계에서 알게 된 것: **매직넘버에 더 많은 소수를 추가해도 탈락률은 logarithmic하게만 증가한다**. 1000개 소수에서 10000개로 늘려도 탈락률은 91% → 95% 정도. 비용 대비 효과가 빠르게 감소.
## 2단계: 비트 패턴에 대한 잘못된 직관
매직넘버 M의 2진 표현을 보다가 가운데에 0이 31개 연속으로 나오는 패턴을 발견했다.
```
...11111[00000000000000000000000000000000000]11...
```
"이걸 활용하면 나눗셈을 shift로 대체할 수 있지 않을까?" 이렇게 생각했다.
**하지만 이 직관은 틀렸다**. 정수론적으로 설명하면:
- 가운데 0 구간이 산술적 의미를 가지려면 매직넘버가 `M_high × 2^k + M_low`에서 `M_low`가 매우 작아야 한다.
- 가운데 0이 있어도 `M_low`가 본체 크기면 mod 연산에 도움이 안 된다.
**진짜로 mod 연산이 빠른 형태**:
- `2^k - 1` (Mersenne): `2^k ≡ 1 (mod M)`
- `2^k + 1` (Fermat-like): `2^k ≡ -1 (mod M)`
- `2^k - c` (c 작음): NIST 곡선들이 이 형태
가운데 0 구간이 길다는 것과 `2^k`에 가깝다는 것은 다른 이야기였다.
## 3단계: M = P × C ≈ 2^k 형태 탐색
진짜 가치 있는 아이디어로 넘어갔다.
> 만약 매직넘버 M이 (작은 소수들의 곱) × (작은 정수)이면서 동시에 2^k에 매우 가깝다면, 합성수 필터 + mod 가속을 둘 다 얻을 수 있다.
이를 정식화하면:
```
M = primorial(N) × C = 2^k + t (|t|가 작음)
```
이런 매직넘버를 어떻게 찾을까? 핵심 통찰은:
**각 (N, k) 쌍에 대해 최적 C는 단 하나**:
```python
C = round(2^k / P) # P = primorial(N)
```
이렇게 만들면 `|M - 2^k| < P/2`가 항상 보장된다.
이 알고리즘의 효율성:
- 9000개 N × 40개 k = 36만 시도
- 각 시도가 빠른 정수 연산
- 0.1초 단위로 결과 도출
## 4단계: 결과들
알고리즘으로 찾은 매직넘버들 (점진적으로):
| ε = log₂(|t|/M) | M 비트 | \|t\| 비트 | 형태 |
|---|---|---|---|
| -32 | 11593 | 11561 | primorial(8161) × 953 |
| -56 | 80292 | 80236 | primorial(55903) × 큰수 |
| -69 | 158 | 99 | primorial(73) × 큰수 |
| -135 | 188 | 53 | primorial(47) × 큰수 |
| -258 | 262 | 5 | primorial(7) × 큰수 |
| -267 | 356 | 89 | primorial(71) × 큰수 |
| -261 | 282 | 21 | primorial(23) × 큰수 |
처음에는 ε이 작은 게 좋은 줄 알았다. 그런데 이게 함정이었다.
## 5단계: 깨달음 - "T가 작은 게 좋은 거지"
매직넘버의 mod 연산 가속 효과를 분석하다 깨달았다.
```
M = 2^k - t (또는 + t)
N mod M ≡ a × t + b (where N = a × 2^k + b)
```
mod 연산의 비용은 `a × t` 곱셈에 의존한다. 즉:
- `|t| = 32비트`: 64비트 워드 1개 곱셈, 매우 빠름
- `|t| = 64비트`: 빠름
- `|t| = 128비트`: 약간 느림
- `|t| = 1000비트`: 거의 표준 mod와 같음
**ε(상대 오차)는 수치 자랑일 뿐, 진짜 중요한 것은 |t|의 절대 크기**.
이걸 깨닫고 결과를 다시 보니:
| ε | M 비트 | \|t\| 비트 | mod 가속 가능성 |
|---|---|---|---|
| -32 | 11593 | 11561 | 없음 |
| -56 | 80292 | 80236 | 없음 |
| -135 | 188 | 53 | 가능 |
| -258 | 262 | 5 | 가능 |
ε이 더 작아 보이는 -56이 -135보다 *못한* 매직넘버였다. |t|의 절대 크기가 핵심이었다.
## 6단계: Trade-off 곡선 발견
알고리즘의 한계를 분석하니 명확한 패턴이 보였다.
```
|t| < P/2 (항상 보장)
```
즉:
- P를 작게 잡으면 → |t|도 작음 → mod 가속 좋음
- 하지만 P 작으면 → 포함된 소수 수 적음 → 합성수 필터 약함
**Trade-off 곡선**:
| primorial | P 비트 | \|t\| 최대 | 포함 소수 | 탈락률 |
|---|---|---|---|---|
| primorial(7) = 210 | 8 | ~7비트 | 4개 | 77% |
| primorial(13) | 15 | ~14비트 | 6개 | 81% |
| primorial(29) | 34 | ~33비트 | 10개 | 86% |
| primorial(47) | 60 | ~59비트 | 15개 | 89% |
| primorial(71) | 102 | ~101비트 | 20개 | 91% |
|t|를 작게 만들면 합성수 필터가 약해지고, 강한 필터를 원하면 |t|가 커진다. **두 마리 토끼는 잡기 어렵다**.
이건 Baker's theorem이라는 정수론적 결과와 연결된다. primorial × C가 2^k에 매우 가까울 수 있는 정도에 이론적 한계가 있다.
## 7단계: 벤치마크 - 진짜 빠른가?
이론은 좋았다. 그럼 실제로 빠른가?
10000개 1024비트 무작위 후보로 측정:
### 합성수 필터 측정
```
trial div 2~47 (15개 소수): 1924ns/후보
gcd M_47 (math): 1300ns/후보 → 1.48x 빠름
gcd M_47 (gmpy2): 1166ns/후보 → 1.65x 빠름
gcd M_1016 (math): 4468ns/후보 → 0.43x 느림
```
**결과**: 작은 매직넘버는 trial division보다 1.5배 빠름. 큰 매직넘버는 오히려 느림.
탈락률은 거의 같음 (트라이얼과 매직넘버가 같은 소수 집합 검사).
### Mod 가속 측정 (충격적인 결과)
|t| = 53비트의 -135 매직넘버를 활용한 mod 연산:
```
n % M_47 (Python 표준): 593ns/후보
magic_mod M_47 (-135): 2747ns/후보 → 표준보다 4.6배 *느림*
```
**충격**. 이론적으로 빨라야 하는데 4배 이상 느렸다.
## 8단계: 왜 magic_mod가 느린가?
원인을 분석했다.
### 원인 1: Python의 % 연산이 이미 GMP 사용
CPython 3.5+의 큰 정수 산술은 내부적으로 매우 최적화되어 있다. `n % M` 한 번 호출이면 단일 C 라이브러리 호출로 끝난다.
본인 magic_mod는:
- Python 인터프리터에서 while loop 실행
- 각 반복마다 shift, 곱셈, 뺄셈
- 인터프리터 오버헤드 누적
**알고리즘이 이론적으로 적은 연산을 한다 ≠ Python에서 빠르다**.
### 원인 2: 188비트는 GMP에게 작은 수
GMP의 강점은 매우 큰 수에서 나타난다. 188비트는 3개 64비트 워드 정도로 GMP에게는 직접 처리 가능한 크기. magic_mod의 알고리즘 복잡함이 이득을 못 준다.
### 원인 3: 반복 횟수
1024비트 n을 188비트로 줄이려면 약 6~7번 반복. 6~7번의 Python 연산 vs 1번의 C/GMP 호출. 후자가 압승.
## 결론: 정직한 평가
며칠간의 작업 후 정직한 평가:
### 작동하는 부분
- **합성수 필터로서 1.5배 가속**: 작은 매직넘버 (50~200비트)에서 trial division보다 빠름
- **이론적으로 mod 가속 가능**: |t| 작은 매직넘버 발견 가능
- **알고리즘 자체는 효율적**: 0.1초 단위로 매직넘버 후보 탐색
### 작동하지 않는 부분
- **Python에서 mod 가속**: 표준 % 연산이 이미 최적화되어 있어 magic_mod가 더 느림
- **"빠른 소수 판정법"이라는 표현**: 사전 필터의 작은 가속은 전체 소수 판정 시간에 미치는 영향이 미미
- **압도적 새 발견**: 본질적으로 알려진 trade-off 곡선 위의 점들
### 학습 가치
- primorial과 정수론적 구조 깊이 이해
- 효율적 검색 알고리즘 작성
- ε vs |t|의 차이 직접 깨달음
- **이론과 실제의 차이**를 직접 측정으로 확인
## 인류에게 도움되는 발견의 조건
며칠간 매직넘버를 찾으며 "인류에게 도움될" 수치 조건을 정리해봤다.
### 조건 A: 임베디드 응용 가속
- M ≈ 256비트
- |t| ≤ 32비트, 워드 정렬
- 합성수 필터 80%+
- **실측으로 표준 ECC 라이브러리보다 빠름**
### 조건 B: RSA 키 사전 필터
- M ≈ 500~2000비트
- 포함 소수 100개+ (탈락률 92%+)
- 표준 trial division보다 측정 가능하게 빠름
### 조건 C: 이론적 새 발견
- 알려진 정수론적 한계를 깨는 결과
- 매우 어려움 (박사과정+ 수준)
가장 현실적인 길은 **A**. 본인 매직넘버를 임베디드 환경 (ESP32 등)에서 C로 재구현하고 측정해야 진짜 가치 확인 가능.
## 배운 것
이 탐색에서 가장 큰 학습은 **자신의 직관을 정확히 검증하는 것**이었다.
- "비트 패턴이 특별하면 빠를 것이다" → 틀림
- "ε이 작으면 좋은 매직넘버" → 부분적 진실, |t|가 더 본질
- "이론적으로 빠른 알고리즘은 실제로도 빠르다" → Python에서는 자주 틀림
- "더 많은 소수를 포함하면 더 좋다" → 비용 vs 효과의 한계점 존재
직관은 출발점이고, 검증은 종착점이다. 둘 다 필요하다.
## 다음 단계
이 작업을 어떻게 마무리할지 고민 중이다.
**옵션 1**: 현재 결과로 마무리. 학습 가치 충분.
**옵션 2**: C/Rust로 magic_mod 재구현. Python overhead 제거 후 다시 측정. 만약 빠르면 의미 있는 결과.
**옵션 3**: ESP32 같은 임베디드 환경에서 측정. 환경이 다르면 결과가 다를 수 있음.
어느 길이든 시작점은 정직한 자기 평가다. 그게 이번 작업의 진짜 결과다.
## 참고: 사용한 도구
- Python (표준 int 연산)
- math.gcd, gmpy2 (비교)
- 외부 라이브러리 없이 표준 환경
- 개인 PC, RTX 5070 Ti GPU (탐색용)
## 마치며
매직넘버 하나 더 찾기는 쉽다. 하지만 자신이 만든 도구의 진짜 가치를 정직하게 평가하는 게 더 어려웠다. 이 글이 비슷한 호기심을 가진 누군가에게 도움이 되길 바란다.
가장 큰 교훈: **이론적 빠름과 실제 빠름은 다르다. 측정하라**.<br>
댓글
댓글 쓰기