소수 판별

1 개요

primality test

소수 판별, 소수판별법, 소수 판정

• 어떤 자연수 n이 소수인지 합성수인지를 판정하는 문제
• RSA암호의 키 생성 등에서 소수 판정이 중요함

소수인지를 빠르게 판정하는 알고리즘은 암호학, 계산이론에서 주요 관심 대상임

2 주요 방법

• AKS 소수판별법 ★
• 밀러-라빈 소수판별법 ★
• 뤼카-레머 소수판별법
• 페팽 소수판별법

3 같이 보기

• 소수(prime number)
• 함수 is_prime()

4 참고

• 위키백과 "소수 판별"
• 영어 위키백과 "Primality test"
• 다음백과 "소수 판별"
• 네이버백과 "소수 판별"