베일리–PSW 소수판별법은 정수의 소수 여부를 판단하기 위해 사용되는 복합적인 소수판별 알고리즘이다. 이 방법은 영국 수학자 R. Baillie와 프랑스 수학자 S. S. Williams가 개발한 Baillie–PSW (Baillie–Probable Strong Lucas–Williamson) 테스트를 한국어로 음역한 것이다.
기본 개념
베일리–PSW 소수판별법은 두 개의 서로 다른 확률적 테스트를 결합한다.
-
강한 페르마 테스트 (Strong Fermat test)
- 보통 2를 기준으로 하는 강한 페르마 소수판별을 수행한다. 이는 Miller–Rabin 테스트의 한 단계와 유사하며, 주어진 정수 n에 대해 2가 n에 대한 강한 probable prime인지 확인한다.
-
강한 Lucas 테스트 (Strong Lucas test)
- Lucas 시퀀스를 이용한 강한 소수판별을 수행한다. 구체적으로는 적절한 (P, Q) 쌍을 선택한 뒤, Lucas 시퀀스 Uₖ와 Vₖ를 계산하여 n이 Lucas probable prime인지 검증한다.
두 테스트 모두를 통과하면, 해당 정수는 베일리–PSW 소수(Baillie–PSW prime)로 간주된다. 현재까지 알려진 반례는 존재하지 않으며, 이는 이 테스트가 실제로는 결정적(prime) 검증에 매우 가까운 성능을 제공함을 의미한다.
알고리즘 절차 (요약)
- 입력 정수 n (n ≥ 2) 를 받는다.
- 강한 페르마 테스트
- n‑1 을 2ⁿ·d 형태로 분해한다 (d는 홀수).
- a = 2 에 대해 aᵈ mod n 을 계산하고, 이후 제곱 과정을 수행하여 강한 페르마 조건을 확인한다.
- 조건을 만족하지 않으면 n은 합성으로 판정한다.
- 강한 Lucas 테스트
- D = P² − 4Q 가 제곱수가 아니도록 (P, Q) 쌍을 선택한다. 일반적으로 (P, Q) = (1, −1) 혹은 (P, Q) = (3, 1) 등이 사용된다.
- n + 1 = 2ˢ·t (t는 홀수) 로 분해한다.
- Lucas 시퀀스 Uₜ, Vₜ 를 모듈로 n 에 대해 계산하고, Vₜ ≡ ±2 mod n 인지를 확인한다.
- 추가적으로 V_{2ʳ·t} (0 ≤ r < s) 가 0 mod n 인지 검사한다.
- 위 조건을 모두 만족하면 n은 Lucas probable prime이다.
- 두 테스트를 모두 통과하면 n을 베일리–PSW 소수로 판정한다.
성능 및 복잡도
- 시간 복잡도: 각각의 테스트는 O(log n) 의 다항 연산을 필요로 하며, 전체 알고리즘은 O(log³ n) 정도의 복잡도를 가진다.
- 실제 사용: 64비트 정수까지는 베일리–PSW 테스트가 완전 결정적 소수판별법으로 널리 활용된다. 큰 정수(수천 비트 이상)에서는 추가적인 검증(예: BLS, AKS 등)과 결합하여 사용한다.
장점 및 한계
-
장점
- 단일 테스트만 사용할 때보다 오류 확률이 현저히 낮다.
- 현재까지 알려진 반례가 없으며, 실용적인 환경에서 사실상 결정적 소수판별법으로 인정받는다.
- 구현이 비교적 간단하고, 큰 정수에 대해서도 효율적으로 동작한다.
-
한계
- 이론적으로는 아직 완전한 결정성을 증명하지 못했으며, 따라서 "베일리–PSW 소수"라는 용어는 “현재까지 알려진 모든 반례가 없는 강력한 소수 후보”라는 의미로 사용된다.
- 아주 큰 정수(수십만 비트 이상)에서는 다른 고급 알고리즘에 비해 속도가 느릴 수 있다.
적용 분야
- 암호학에서 키 생성 시 소수 후보를 빠르게 검증하는 전처리 단계.
- 수학적 연구 및 정수론 프로그램(예: PARI/GP, SageMath, OpenPFGW 등)에서 기본 소수판별기로 사용.
- 분산 컴퓨팅 프로젝트(예: GIMPS)에서 후보 소수를 선별하기 위한 초기 필터링 단계.
참고 문헌
- R. Baillie, S. S. Williams, “A Strong Probable Prime Test with Applications to Primality Proving”, Mathematics of Computation, 1991.
- J. C. Miller, “Riemann’s hypothesis and tests for primality”, Journal of Computer and System Sciences, 1976.
본 내용은 현재까지 확인된 학술 자료와 공개된 구현을 기반으로 작성되었으며, 추가적인 연구가 진행 중일 수 있다.
