알고리즘26

randomization 알고리즘은 determination 알고리즘에 비해서 약하다.

왜? 간단한 게 별로 없다. 확률 계산이 정확해야 한다.

 

소인수분해는 너무 느리다.

n이 있으면 2로 나눠보고 3으로 나눠보고...n-1까지 나눠본다. 하나도 나눠지지 않으면 소수 => 굉장히 느리다

 

입력은 숫자 한개 n 인데

예를 들어 367이라면 367번 계산? O(n)? 너무 느리다.

 

숫자가 작고 크고에 따라 시간이 다르지만, 주어진 숫자가 32비트 이하라면 시간이 똑같다고 쳐도 되는 수준

예를 들어 merge sort의 경우

n개 숫자 크기와 상관없이 갯수만 가지고 O(nlogn)이라고 말할 수 있다.

정확히 말하면 O(nlogn x s) -> s는 숫자 두 개를 비교하는 시간

주어진 숫자의 범위가 1~m이라면 s = log m

 

사실 입력은 하나인데 1이라고 쓰기 그러니까 n으로..

정확히 말하면 log(n) bit , 어쨌든 n이 나오면 굉장히 느린 것이라는거~

 

O(루트n) 짜리 방법도 있다.

1,2,3...,a,a+1,...,b,...n (정수)

a와 a+1사이에 루트n이 있다.(실수)

1부터 a까지만 체크해봐도 된다. (n을 해당 수로 나눈다.)

 왜? 만약 n이 b로 나눠진다고 하면 n=bc 라고 표현할 수 있음

하지만 이때 c는 어차피 루트n보다 작음

 

제곱을 7로 나눈 나머지만 보겠다.

 

마지막줄이 전부 1? 7은 prime

 

6은 prime이 아니다.

 

=> 페르마의 정리

if n is prime, a^(n-1) = 1 mod n

1<a<n

prime n=7일때 a^6 = 1

 

사실은 아니지만 일단 믿자

 

35가 8379가 prime이 아니라는 증거가 된다.

 

모든 prime이 아닌 숫자는 증거가 있냐?

아니다.

Carmichael number가 예외이다.

하지만 아주 드물고, Carmichael number를 확인하는 방법이 있다.

 

 

 

만약 8379가 prime이 아니라는 WITNESS가 35 딱 한 개라면?

prime이 아니라는 것을 알아낼 확률이 굉장히 낮다. => 실제로 쓰기 힘들다

 

최소 하나의 witness가 있으면(prime이 아니면) Zn*는 2,3,...n-1 중 절반 이상이 witness

 

random 프라임을 찾는 프로세스이다.

 

1. n이 Carmichael 인지 test한다. => 맞다면 소수 아님

2. a,n의 최대공약수를 구해서 1인지 검사한다. => 1이 아니면 소수 아님

3. a^(n-1) =1 mod n 확인 => 1이면 반복, 아니면 소수 아님

 

저 테스트를 다 끝나면 prime이다.

한 번의 테스트를 통과할 확률이 1/2이므로

k번 테스트를 통과할 확률은 1/2^k

k가 100이라면 로또를 하나씩 사서 4주연속 당첨될 확률ㅋ

1000이라면 로또 43주연속 당첨ㅋ

이정도 확률은 실제로 생길 확률이 아님. 피할 수 있는 확률이 아님