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[00000000000000000000000000...