밀러-라빈 소수 판별법
밀러-라빈 소수 판별법은 홀수 정수가 소수인지 모듈러 거듭제곱과 강한 의사소수 검사를 이용해 판정한다 확률적 소수 판정 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한...
| 분류 | 알고리즘 · 확률적 소수 판정 |
|---|---|
| 핵심 문제 | 홀수 정수가 소수인지 모듈러 거듭제곱과 강한 의사소수 검사를 이용해 판정한다 |
| 방법 | n-1=2^s d로 분해하고 밑 a에 대해 a^d mod n과 연속 제곱의 값을 검사한다 |
| 계산 비용 | 검사 밑 수 k와 모듈러 곱 비용에 의존하며 대략 O(k log n)번 모듈러 곱 |
| 적용 조건 | n>2의 홀수 및 정밀한 정수 곱·거듭제곱이 필요하며 밑의 선택에 따라 확률적·결정적 결과가 달라진다 |
| 관련 활용 | 대형 정수의 소수 후보 검사·암호 키 생성 과정에 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
밀러-라빈 소수 판별법은 홀수 정수가 소수인지 모듈러 거듭제곱과 강한 의사소수 검사를 이용해 판정한다 확률적 소수 판정 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 n-1=2^s d로 분해하고 밑 a에 대해 a^d mod n과 연속 제곱의 값을 검사한다. 합성수 증인을 찾으면 즉시 합성수로 판정한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 검사 밑 수 k와 모듈러 곱 비용에 의존하며 대략 O(k log n)번 모듈러 곱 적용 전제는 n>2의 홀수 및 정밀한 정수 곱·거듭제곱이 필요하며 밑의 선택에 따라 확률적·결정적 결과가 달라진다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 대형 정수의 소수 후보 검사·암호 키 생성 과정에 사용한다. 범위가 제한된 64비트 정수에서는 알려진 고정 밑 집합으로 결정적 판정이 가능하다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]