| [[이론 컴퓨터 과학|'''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"]] | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36,#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 정보 엔트로피 · 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타프로그래밍 · 람다 대수 · 유형 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 구문 트리(완전 구문 트리 · 추상 구문 트리) · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set) · 트리^레드-블랙 트리, B-트리, 힙, 피보나치 힙^ · 큐 · 스택 | ||||
| 수학적 최적화 | <keepall> 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| <keepall> 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| <keepall> 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성 | ||||
| <keepall> 대칭키 암호화 방식 | 블록 암호 알고리즘(파이스텔 네트워크 · DES · AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| <keepall> 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
밀러-라빈 소수판별법(Miller-Rabin primality test)[1]은 입력으로 주어진 수가 소수인지 아닌지 페르마의 소정리를 변형하여 확률적으로 판별하는 알고리즘이다.2. 원리
페르마의 소정리에 의하여 [math(p)]가 소수이면 임의의 정수 [math(a)]에 대하여 [math(a^p\equiv a\pmod p)]가 성립하고, [math(a)]와 [math(p)]가 서로소이면 [math(a^{p-1}\equiv 1\pmod p)]이 성립한다.[math(p)]가 홀수 소수라면 [math(p - 1 = d \times 2^s)] 라 할 수 있고([math(s)]는 양의 정수, [math(d)]는 홀수), [math(a^{p-1}\equiv 1\pmod p)]는 곧 [math(a^{d \times 2^s}\equiv 1\pmod p)]이다.
소수 [math(p)]에 대하여 [math(x^2\equiv 1\pmod p)]이면 [math(x^2 - 1 \equiv (x-1)(x+1) \pmod p)]에서 [math((x-1) \equiv 0 \pmod p)] 이거나 [math((x+1) \equiv 0 \pmod p)]이다. 즉 [math(x \equiv 1 \pmod p)] 이거나 [math(x \equiv -1 \pmod p)]이 성립한다.
[math(a^{d \times 2^s}\equiv 1\pmod p)]이 성립한다고 하면 [math(a^{d \times 2^{s-1}}\equiv 1\pmod p)]이 성립하거나 [math(a^{d \times 2^{s-1}}\equiv -1\pmod p)]이 성립한다.
[math(a^{d \times 2^{s-1}}\equiv 1\pmod p)]이 성립하는 경우에는 [math(a^{d \times 2^{s-2}}\equiv 1\pmod p)]이 성립하거나 [math(a^{d \times 2^{s-2}}\equiv -1\pmod p)]이 성립한다.
[math(a^{d \times 2^{s-2}}\equiv 1\pmod p)]이 성립하는 경우에는 [math(a^{d \times 2^{s-3}}\equiv 1\pmod p)]이 성립하거나 [math(a^{d \times 2^{s-3}}\equiv -1\pmod p)]이 성립하고...이를 반복하면 [math(a^{d} \equiv 1\pmod p)]가 성립하거나 [math(0 \leq r < s)]인 어떤 정수 [math(r)]에 대하여 [math(a^{d \times 2^{r}} \equiv -1\pmod p)]이 성립하게 된다.
따라서 어떤 홀수[2] [math(N)]이 소수인지 판단하고 싶다면, [math(N- 1 = d \times 2^s)]로 분해한 뒤 먼저 [math(a^{d} \mod\ N)]를 구하여 [math(a^{d} \equiv 1\pmod N)]이거나 [math(a^{d} \equiv -1\pmod N)]인지 판단하고, 맨 처음 구한 [math(a^{d} \mod\ N)]을 이용하여 [math(a^{d \times 2^{r}} \mod\ N)]을 차례대로 구하고 [math(a^{d \times 2^{r}} \equiv -1\pmod N)]이 성립하는지 판단하면 된다.
이렇게 판단하면 페르마의 소정리보다 더 강력하게 소수를 걸러낼 수 있다. [math(a = 2)], [math(N = 645 = 3 \times 5 \times 43)]이라 하면 [math(a^{N - 1} \equiv 1 \pmod N)]이 성립하여 [math(N)]을 소수라고 판단할 위험이 있으나, [math(N - 1 = 161 \times 2^2)]에서 [math(a^{161 \times 2^{0}} \equiv 257 \pmod N)], [math(a^{161 \times 2^{1}} \equiv 259 \pmod N)]가 되어 페르마의 소정리에서는 소수일 수 있다고 판단했지만, 밀러-라빈 소수판별법에서는 합성수라고 판단했다.