논문 요약: 211 까지의 47 개 소수 기저에 대한 오일러 의사소수 생성

1. 문제 제기 (Problem)

• 배경: RSA 및 Diffie-Hellman 과 같은 공개키 암호 시스템은 대규모 소수 생성에 의존합니다. 소수 판별은 계산 비용이 크기 때문에, 실제로는 솔로베이 - 스트라센 (Solovay-Strassen) 또는 밀러 - 라빈 (Miller-Rabin) 과 같은 확률적 합성수 판별 테스트를 사용합니다.
• 위협: 이러한 테스트는 특정 기저 (base) 에 대해 소수처럼 행동하는 합성수, 즉 의사소수 (pseudoprime) 를 통과시킬 수 있습니다. 만약 적대적 공격자가 이러한 의사소수를 알고 있다면, 사용자를 속여 합성수를 소수로 받아들이게 할 수 있습니다.
• 목표: 본 논문은 오일러 의사소수 (Euler pseudoprimes) 에 초점을 맞추고 있습니다. 오일러 테스트는 $n$이 합성수임에도 불구하고 특정 기저 $a$에 대해 $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$을 만족하는 수를 의미합니다.
• 핵심 질문: "얼마나 많은 연속된 소수 기저 (prime bases) 를 통과하는 오일러 의사소수를 찾을 수 있는가?"

2. 방법론 (Methodology)

가. 카르마이클 수 (Carmichael Numbers) 의 분류 및 분석

• 저자들은 오일러 의사소수의 후보로 카르마이클 수 (모든 기저 $a$에 대해 $a^{n-1} \equiv 1 \pmod n$을 만족하는 합성수) 를 선정했습니다.
• 카르마이클 수를 카르마이클 람다 함수 ($\lambda(n)$) 와 인덱스 ($i(n) = \frac{n-1}{\lambda(n)}$) 를 기반으로 세 가지 클래스로 분류했습니다.
  • Class A: 인덱스 $i(n)$이 짝수인 경우. 이 클래스는 이론적으로 가능한 최대인 $\phi(n)/2$개의 오일러 거짓말꾼 (Euler liars) 을 가집니다.
  • Class B: 인덱스 $i(n)$이 홀수인 경우. 이는 다시 $B1$과 $B2$로 세분화되며, 오일러 거짓말꾼의 비율이 Class A 보다 낮습니다.
• 결론: Class A 에 속하는 카르마이클 수가 가장 많은 기저를 통과할 가능성이 높으므로, 연구의 주된 대상이 되었습니다.

나. 오일러 의사소수의 곱셈을 통한 확장 알고리즘

• 기존에 발견된 오일러 의사소수들을 서로 곱하여 더 크고 더 강력한 (더 많은 기저를 통과하는) 의사소수를 생성하는 알고리즘을 개발했습니다.
• 핵심 전략:
  1. 동일한 기저까지 생존하는 수들의 곱: $epsp(a)$(기저$a$까지 통과하지만 다음 소수에서는 실패하는 수) 집합 내에서 두 수를 곱할 때, 두 수 모두 Class A 에 속하고 동일한 기저 $a$까지 통과하는 경우, 그 곱은 최소한 다음 소수 기저까지 통과할 가능성이 매우 높다는 것을 증명했습니다 (Lemma 13).
  2. 필터링: 작은 소인수 (150 미만) 를 가진 수는 제외하여, 기저가 소인수일 때 테스트가 실패하는 경우를 방지했습니다.
  3. 효율적인 검증: 곱셈 후 카르마이클 수 조건 ($\lambda(n) | (n-1)$) 과 Class A 조건을 빠르게 확인하고, Jacobi 기호만 계산하여 통과 기저를 확장해 나갔습니다.

다. 점진적 생성 (Iterative Construction)

• Atomic (원자) 수: 더 이상 카르마이클 수의 곱으로 분해되지 않는 카르마이클 수를 기반으로 시작했습니다.
• 계층적 곱셈:
  • $epsp_2(a)$: 두 개의 원자 수의 곱.
  • $epsp_4(a)$: 두 개의 $epsp_2(a)$ 수의 곱.
  • $epsp_8(a), epst_{16}(a)$ 등으로 점진적으로 크기를 키우며 기저를 확장했습니다.
• 최적화: 생성된 수들의 소인수가 겹치지 않아 제곱인수 (square-free) 조건을 만족하도록 소인수 크기를 점진적으로 늘려가며 (150 $\to$ 200 $\to$ 300) 검색 범위를 조정했습니다.

3. 주요 기여 (Key Contributions)

1. 카르마이클 수의 정밀한 분류: 오일러 거짓말꾼의 수를 결정하는 카르마이클 수의 새로운 분류 체계 (Class A, B1, B2) 를 제시하고, 각 클래스별 이론적 한계를 증명했습니다.
2. 효율적인 생성 알고리즘: 이미 발견된 오일러 의사소수를 곱하여 더 강력한 수를 찾는 알고리즘을 제안하고, 이를 통해 대규모 계산을 최적화했습니다.
3. 기록적인 오일러 의사소수 발견: 47 개의 연속된 소수 기저 (2 부터 시작하여 211 까지) 를 모두 통과하는 오일러 의사소수를 최초로 발견했습니다.
4. Sophie Germinus 의사소수 제안: 카르마이클 수 외에 $n = p_1(2p_1-1)$ 형태 ($p_1, 2p_1-1$이 소수) 의 새로운 합성수 유형을 제안하고, 이것이 $\phi(n)/4$개의 오일러 거짓말꾼을 가진다는 것을 증명했습니다.

4. 결과 (Results)

• 최고의 성과: 1230 비트 크기의 합성수를 발견했습니다. 이 수는 2 부터 211 까지의 모든 정수 기저 (총 47 개의 소수 기저) 에 대해 오일러 테스트를 통과합니다.
  • 이전 기록 (Sorenson & Webster) 은 밀러 - 라빈 테스트에서 12 개의 소수 기저를 통과하는 것이었습니다.
  • 솔로베이 - 스트라센 테스트의 실패 확률이 밀러 - 라빈보다 높음 (최대 1/2 vs 1/4) 을 고려할 때, 47 개 기저 통과라는 결과는 매우 인상적입니다.
• 통계적 분석:
  • 발견된 오일러 의사소수들의 98% 이상이 Class A 에 속하며, $n \equiv 1 \pmod{120}$인 경우가 압도적으로 많음을 확인했습니다.
  • 곱셈 과정에서 Class A 수들끼리만 곱하는 전략이 성공률을 극대화함을 실험적으로 입증했습니다.
• 데이터: 37 이상의 기저를 통과하는 129,092 개의 오일러 의사소수와, 이를 기반으로 생성된 수백만 개의 후보군을 분석했습니다.

5. 의의 (Significance)

• 암호학적 안전성 평가: 이 연구는 확률적 소수 판별 테스트 (특히 Solovay-Strassen) 가 적대적 환경에서 얼마나 취약할 수 있는지를 보여줍니다. 공격자가 이러한 고강도 의사소수를 생성할 수 있다면, 무작위 소수 생성 프로세스가 완전히 무력화될 수 있음을 시사합니다.
• 이론적 통찰: 카르마이클 수의 구조와 오일러 테스트의 관계에 대한 깊은 이해를 제공하며, 수론적 성질 (Jacobi 기호, 카르마이클 람다 함수) 을 활용한 의사소수 생성의 새로운 패러다임을 제시합니다.
• 알고리즘적 발전: 단순한 브루트 포스 검색을 넘어, 수의 구조적 특성을 이용한 계층적 곱셈 알고리즘은 향후 더 큰 규모의 의사소수 탐색에 표준적인 접근법이 될 수 있습니다.

결론적으로, 이 논문은 카르마이클 수의 구조적 분류를 기반으로 한 효율적인 알고리즘을 통해, 47 개의 연속된 소수 기저를 통과하는 역사상 가장 강력한 오일러 의사소수를 발견함으로써, 현대 암호학의 소수 판별 테스트에 대한 새로운 도전과제를 제시했습니다.