Forisek–Jancina 방식으로 32비트 정수를 빠르게 소수 판정하기

AI 요약

Forisek와 Jancina의 2015년 논문은 기계어 크기에 맞는 정수를 대상으로 결정론적 소수 판정법을 소개합니다. 글에서는 32비트 구현을 중심으로 설명하며, 소수 후보를 먼저 작은 소수로 나눈 뒤 해시값으로 검사용 밑을 선택하고 강한 probable-prime(SPRP) 검사를 수행합니다.

32비트 구현

코드는 2, 3, 5, 7로 나누어지는 수를 먼저 걸러냅니다. 121보다 작은 수는 이 단계에서 바로 판정합니다. 그보다 큰 수는 입력값에 해시 연산을 적용해 256개 항목 가운데 밑 하나를 고릅니다. 선택한 밑으로 Miller–Rabin 방식의 SPRP 검사를 수행하며, 각 항목은 16비트 정수라 조회 테이블은 512바이트를 차지합니다. 이 구현은 uint64_t 중간 연산으로 모듈러 곱셈을 처리합니다. 글은 논문이 64비트 정수용 판정법도 다룬다고 소개하지만, 코드 예제는 32비트용입니다.

Reddit 반응

• @u/DataBaeBee — Forisek과 Jancina 방식은 작은 정수를 위한 결정론적 소수 판정법입니다. 확률적 판정법이 아니며, 매우 빠르고 구현하기도 쉽습니다. 32비트 정수라면 512바이트 조회 테이블과 몇 번의 덧셈·곱셈만으로 소수를 판정합니다.
  • @u/feldrim — 드디어 AI 이야기가 아닌 수준 높은 컴퓨터과학 작업이 나왔네요. 발표를 축하하고 공유해 주셔서 감사합니다.

원문: Reddit / 번역·요약: Trawling