| [ QuizWit ] in KIDS 글 쓴 이(By): guest (QMI) <dormael.kisa.or.> 날 짜 (Date): 2000년 5월 9일 화요일 오후 09시 00분 59초 제 목(Title): Re: 솟수에 대한 질문... 안녕하세요. 간혹 이곳에 들러 재미있는 Quiz를 발견하곤 하는데 글은 잘 쓰지 않았습니다. 소수에 관한 질문, 즉 아주 큰 수 n의 바로 아래위의 소수가 뭔지를 아는 것이 쉬운가 하는 질문은 요즘 제가 공부하는 것과 좀 관련이 있어 추가 설명을 드리고자 합니다. 일단 수학적인 입장에서 보면 n의 바로 위 아래 수가 뭐냐의 답은 n으로 표현 되어야만 해가 있는 것으로 봅니다. (약간의 의견차이는 있겠지만 ^^) 즉 n으로 표시되지 않는 다면 case by case로 해가 달라지므로 별로 의미 없는 것입니다. 주어진 n에 대하여 그냥 위 아래 소수를 구하라고하면 그냥 1씩 빼거나 더하가면서 그 수가 소수인지를 확인하면 됩니다. 이런 대답을 원하신 것은 아니겠죠? 즉 아주 큰 수에 대해서 어떠한 일이 일어나는 가에 관심이 있으신 거죠? 우선 '아주 크다'는 말이 너무 모호하고, '쉬운가' 하는 말 역시 너무 모호하다는 생각이 듭니다. 그래서 쉽다라든가 어렵다는 말을 P나 NP와 같은 용어를 사용해서 표현하고 있습니다. 컴퓨터가 발전된 이 시점에서 컴퓨터로 되는 계산은 우선 쉽다고 봅니다. 그리고 컴퓨터로 계산이 안되는 것은 어렵다고 보는 것이죠. 여기서 P는 다항식(polynomial)의 영문 첫 글자로 n을 2진수로 표현했을 때의 자리수에대한 다항식의 횟수안에 계산 가능한 문제를 말합니다. 예를 들어 n이 소수인지 아닌지는 1부터 n만큼 나누어보면 되므로 반드시 n번 안에 계산할 수 있습니다. 하지만 n이 2^1000인 수라면 2^1000을 계산 해야하는데 너무 시간이 많이 걸리겠죠? 그래서 2^1000을 2진수로 쓰면 1000자리의 수가 되는데 이 1000의 다항식 번안에 계산이 된다면 컴퓨터로도 계산이 가능해지죠. 물론 다항식도 차수가 너무크면 못하는 것은 마찬가지죠. 2^1000문제 ---->> 1000의 다항식문제 만약 n이 소수인지를 알기위해 n번 계산해보아야 한다면 이 문제는 P에 속하지 않는 것이되겠죠. NP는 P 보다는 어려운 문제로 알려져 있습니다. 즉 어떤 판단을 내리는 문제로써 답을 아는 경우에 그 답을 P 안에 다른 사람에게 확인 시켜줄 수 있는 것 입니다. 즉 n=pq인 경우 n을 소인수 분해하는 것은 P문제인지 아닌지 알려져 있지는 않지만 답 p나 q를 아는 경우 n이 p로 나누어 지는 것을 P안에 확인할수 있기때문에 NP문제가 됩니다. NP보다 더 어려운 문제를 NP-hard라고 하면 여기까지가 제가아는 문제의 어려운 정도에 관한 것입니다. 처음 질문하진 문제는 즉 n이 아주 큰 경우에, 즉 2^1000정도라고 하고, 그 수가 소수이지 아닌지를 판별하는 것은 P문제이므로 1000의 다항식 안에 풀수 있습니다. 하지만 이 다항식이 더무 커서 보통은 확률론적인 방법으로 n이 소수인지 아닌지를 판별하게 됩니다. 이 방법은 확실하게 소수인지 아닌지를 말해 주진 않지만 한 100번 정도 확인하면 1/2^100의 에러율로 거의 정확히 판별합니다. 물론 1000번이면 1/2^1000이니까 거의 틀릴 일이 없겠죠. 즉 현실적으로 아주 큰 수에 대해서도(컴퓨터적 수준에서) 바로 위아래 소수를 구하는 것은 P문제 이므로 쉽다고 할 수 있겠습니다. 질문에 대한 대답이 너무 길었죠? 그럼 즐거운 시간 되시길... QMI |