어떤 수가 소수인지 알아내는데 걸리는 시간
글쓴이: totohero / 작성시간: 금, 2007/02/09 - 3:13오후
어떤 수가 소수인지 알아내려면 2부터 그 수의 제곱근까지의 수로 한번씩 나눠보면 될텐데요, 따라서 당연히 P에 속하는 문제 아닌가요?
그런데 Wikipedia를 돌아다니다보니, 2002년에서야 P에 속하는 방법을 찾아내었다는 글을 보았습니다. (Wikipedia 사이트, 제시된 논문) 저의 영어 독해에 문제가 있는지, 저의 P에 대한 이해가 잘못된 건지 저의 무지를 일깨워 주세요.
위의 논문을 보니 N의 제곱근(N의 1/2승)이 아니라 log(N)보다 작거나 같은 시간에 풀어야 P가 된다네요.
Forums:
나눗셈을 하는데에
나눗셈을 하는데에 드는 time complexity가 O(log N)에 비례하기 때문입니다. 정수론, 암호학 등에서 time complexity를 생각할 때에는, input의 갯수도 중요하지만, input의 size가 중요한 경우도 많습니다.
그렇다해도 O(N^1/2 *
그렇다해도 O(N^1/2 * log N) 아닌지요? 역시 P 아닌가요?
소수를 판별하는
소수를 판별하는 것이 P냐 NP냐를 생각할 때에는 size of input에 대해서 P이냐 NP이냐를 생각하는 겁니다. 즉, s(= log N) 자체에 대해서 polynomial인지를 보는 것입니다. (그게 의미가 있기 때문에...)
그리고 나눗셈에 의한 소수 테스트에 대해서..., 좀 더 정확히 말하면 O(N^1/2* log N * log N) 입니다.
k bit (binary) number를 j bit number로 나누는 경우를 생각해 보면, k-j 번 의 뺄셈이 있고, 각각이 j digit이므로 (k-j)*j 번의 연산이 있습니다. 원래 숫자를 n(피제수), m(제수)로 두면, n은 log k 이고, j은 log m이므로, n를 m으로 나누는 데에는 (log n - log m)*(log m) <= log n * log m <= log n * log n 의 연산이 있습니다.
즉, 위에서 s(=log N)으로 표현하면, O((e^s)^1/2 * s * s) 이므로 exponential 입니다.
답변 감사합니다.
답변 감사합니다. 그런데 아직 s(=log N)으로 정의하는 것이 선뜻 이해안되네요. 정수론 등에서 input N의 size는 항상 log N으로 가정하는 것인가요? (engigneer적인 관점에 치우진 생각일지도 모르겠지만) 이건 혹시 input N을 표현하는데 필요한 machine의 resource 크기를 problem size로 보겠다는 의미일까요?
Numbe3s 라는 드라마를 보면
시즌 1중에 Prime Number라는 에피소드가 있습니다. 거기에서 본 바로는.. 엄청나게 큰 수의 소수여부를 판별하는데 수십년이 걸렸다고 하더군요. -.-a
---------------------
Weird, huh?
http://janbyul.com