AKS 소수판별법 계산기
2002년 발표된 최초의 결정적 다항시간 소수판별법(AKS, "PRIMES is in P")의 각 단계를 보여줍니다. 밀러-라빈·페르마 결과와 교차검증했습니다.
97은(는)
소수
5단계: 다항식 합동검사에서 판정됨
계산 방법
- 1판별할 수 n(2 이상 400 이하)을 입력합니다.
- 2완전거듭제곱 배제 → r 탐색 → gcd 검사 → 다항식 합동검사, 어느 단계에서 판정이 났는지 확인합니다.
- 3최종 판정과, 밀러-라빈으로 같은 수를 판별한 결과가 일치하는지 봅니다.
자주 묻는 질문
2002년 Agrawal·Kayal·Saxena가 발표한, 오차 없이(결정적으로) 소수 여부를 다항시간 안에 확정하는 최초의 알고리즘입니다("PRIMES is in P"). edu/miller-rabin-primality-test·edu/fermat-primality-test는 모두 확률적 방법이라 아주 드물게 합성수를 소수로 오판할 여지가 이론상 남아 있는데, AKS는 그런 여지가 전혀 없습니다.
(X+a)ⁿ ≡ Xⁿ+a (mod Xʳ−1, n)이라는 다항식 합동식이 n이 소수일 때만 성립한다는 것을 이용합니다. 이항정리로 (X+a)ⁿ을 전개하면 가운데 항들의 계수(이항계수)가 n이 소수일 때만 전부 n의 배수가 되어 사라지기 때문입니다 — 페르마의 소정리(aⁿ⁻¹≡1)를 다항식으로 확장한 형태입니다.
edu/ackermann·edu/karatsuba-multiply·edu/strassen-multiply처럼 원리를 보여주는 교육용 알고리즘에 가깝습니다. 다항시간이긴 하지만 차수가 높아 실제 암호에 쓰는 큰 수(수백 자리)에는 밀러-라빈 같은 확률적 방법보다 훨씬 느립니다. 그래서 이 계산기도 400 이하의 작은 수만 다룹니다.
① n이 완전거듭제곱(aᵇ 꼴)이면 즉시 합성수. ② n을 법으로 한 곱셈적 위수가 (log₂n)²을 넘는 가장 작은 r을 찾음. ③ 2~r 사이에 n과 최대공약수가 1보다 크고 n보다 작은 수가 있으면 합성수. ④ n≤r이면 소수. ⑤ 그 외엔 몇 개의 a에서 위 다항식 합동식을 직접 확인해 하나라도 어긋나면 합성수, 전부 성립하면 소수입니다.
네, 이 계산기가 다루는 범위(400 이하)에서는 항상 같아야 합니다. AKS는 오판정이 없는 결정적 방법이고 밀러-라빈도 이 범위에서는 결정적인 밑 조합(2,3,5,7,11,13)을 쓰면 오판정이 없기 때문입니다. 다르게 나온다면 계산에 오류가 있다는 뜻입니다.
알아두면 좋은 점
- 교육용으로 400 이하의 수만 다룹니다. r과 다항식 연산량이 n에 비해 크게 줄지 않아 커지면 급격히 느려집니다.
- 같은 n에서 밀러-라빈·페르마 판별 결과와 교차검증했습니다(2~400 전수).
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.