If you're seeing this message, it means we're having trouble loading external resources on our website.

웹 필터가 올바르게 작동하지 않으면 도메인 *. kastatic.org*.kasandbox.org이 차단되어 있는지 확인하세요.

주요 내용

페르마의 소수 판별법

왜 그리고 어떻게 판별법이 작동하는지 간단히 알아봅시다. 만든 이: Brit Cruise

대화에 참여하고 싶으신가요?

영어를 잘 하시나요? 그렇다면, 이곳을 클릭하여 미국 칸아카데미에서 어떠한 토론이 진행되고 있는지 둘러 보세요.

동영상 대본

우리의 목표는 우리가 정의 할 수 있는 형태로 매우 높은 정확도를 가지면서 입력된 어떠한 수가 함성수임을 혹은 아니면 소수임을 증명을 할 수 있는 일련의 작업들을 정의하는 것입니다 그러면서 이 방식은 효율적이어야 하며 어떠한 기계에서도 빠르게 수행되어야 합니다 심지어 입력의 사이즈가 점차 증가하여 n이라는 정수가 입력되어도 여전히 빠르게 수행되어야하죠 지금까지 우리는 저수준에서의 모든 소수들과 매우 적은 합성수들에 대한 알려진 패턴을 필요한다는 것을 알게되었습니다 하지만 우리는 이전 비디오에서 페르마의 소정리에 대한 시각적인 시연을 해보았습니다 그리고 이는 우리에게 아주 재미있는 규칙을 보여주었습니다 주어진 어떠한 소수 'p'와 그리고 'p'보다 작은 어떠한 다른 정수 'a'가 있다면 우리는 이제 'p'는 'a'의 'p'제곱하여 a를 뺀 값을 나누것을 알고있습니다 간단하게 써보면 a^p = a mod p와 같다고 쓸 수 있겠죠 이를 정리해보면 다음과 같이 볼 수있죠 'p'가 소수이기 때문에 a 와 p는 공통 인수를 가질수 없고 때문에 우리는 소거법을 사용하여 종종 이를 다음과 같이 적을 수 있습니다 a^(p -1) = 1 mod p 그리고 기억하세요 이 작업은 오로지 a와 p의 최대 공약수가 1일때 가능합니다 여기서 우리는 먼저 가능한 몇가지 시연을 해볼겁니다 먼저 이 식의 실행을 보며 익숙해지세요 여기서도 볼 수 있듯이 만일 제가 p에 소수를 넣는다면 그 결과는 항상 1이 됩니다 제가 무엇을 고르더라도 상관 없어요 만일 P에 합성수를 넣게 된다면 우리는 1이 아닌 것을 보게 되겠죠 그러므로 언제든지 위 식의 결과가 1이 아닌 무언가가 나온다면 우리는 그것이 합성수라는 '증거'를 가지게 되는 것이겠죠 이것은 지금 우리가 고른 'p'가 소수가 아님을 증명하고 있습니다 그리고 그것이 이 테스트의 본질이지요 더욱 깊이 알아보기 전에 뒤로 조금 돌아가서 지금까지 여러분들에게 보여드린 패턴을 이용하여 이 테스트의 틀을 한번 만들어보죠 이 테스트에서 우리는 입력값으로 어떠한 정수 'p' 를 제공하고 다음으로는 'p' 보다 작은 임의의 정수 'a' 를 하나 만듭니다 이제 다음과 같이 물어 볼 수 있어요 " 'a'와 'p'의 최대 공약수가 1인가요? " 만일 'a'와 'p'의 최대 공약수가 1보다 큰 값을 가진다면 그들은 공약수를 가지고 있다는 것을 의미 합니다 그리고 우리는 약수를 가지고 있으니 'p' 가 합성수인 것을 증명한 것이지요 그 다음에 작업을 중단하고 종료할 수 있습니다 그리고 우리의 알고리즘은 '합성수'라는 결과를 출력할 것입니다 하지만 만일 아까 했던 질문의 대답이 '예' 이면 다음과 같은 핵심 질문을 할 수 있을 것입니다 " 'a'의 (p-1)제곱과 'p'의 나머지연산의 결과가 1인가요? " 만일 그렇지 않다면 우리는 'p'가 합성수라는 증거를 가지게 되고 현재 하던 작업을 중단한 다음 "다 해봤는데 'p'는 합성수였어" 라고 말할 수 있습니다 그렇지 않고 다시 그 대답도 "네, 결과가 1이에요" 라면 그 값은 이제 소수일 것입니다 맞죠? 저는 이제부터 이러한 일런의 작업들을 코드로 작성할 것입니다 그렇게 왼쪽에 페르마의 테스트에 대한 코드를 작성하였고 오른쪽에는 Trial Division 방식으로 테스트를 하도록 했습니다 이런 방식으로 만든 이유는 테스트가 항상 옳은지를 알기 위해서 입니다 대충 보기에 이것은 제대로 작동하는 것 처럼 보입니다 하지만 문제를 하나 찾았네요 511을 넣었을때, 페르마의 테스트는 이를 소수라고 하는 반면 Trial Division 방식은 이를 합성수라고 하고 있습니다 테스트의 결과를 보면 511은 소수 처럼 보이지만 사실은 그렇지 않습니다 다시 우리의 식으로 돌아가서 어떤일이 일어나고 있는지 보겠습니다 이것은 우리가 의사 소수라고 부르는 경우입니다 즉 이것은 합성수입니다 하지만 우리는 결과가 1이 나오는 이 'a' 들을 고를 수 있습니다 여전히 틀렸네요 그러므로 이러한 결과가 가 1이 나오는 합성수 'a' 들은 우리는 '바보들'이라고 부를게요 왜냐면 이들은 어리석게도 우리가 그 숫자가 소수라고 생각하도록 하기때문이죠 하지만 우리가 또 다른 a들을 고르기 전까지 이런 '바보들' 대신에 우리는 수 많은 합성수의 증거들을 찾을 수 있다는 것은 알아야 해요 그럼 작업으로 다시 돌아가서 똑같은 논리를 우리가 시용했던 가분성 테스트에서 적용해보죠 이 실험을 통해 우리는 간단하게 그 실험을 몇번 반복하고 매 번 새로운 임의의 수를 생성합니다 잘 된다면 우리는 매번 '바보들'을 고르지 않을 것입니다 지금부터는 '바보들'의 숫자는 반드시 우리가 선택한 그룹 전체의 사이즈로 나눠떨어진다는 것을 증명해볼 것입니다 무슨의미냐면 대부분 우리가 고른 것중에 반이나 전체 숫자들중 반정도가 '바보들' 일 수 있다는 것입니다 그러므로 'a'를 임의로 고른 후에 우리가 원하는 대로 그 수가 합성수인 증거를 찾을 확률은 적어도 1/2입니다 이를 t번 반복한 다음 그 수가 합성수라는 증거를 찾지 못할 확률은 거의 1/(2^t)입니다 그러므로 만일 20번을 시도했다면 소수라고 결과가 잘못 나올 확률은 100만분의 1 보다 작습니다 이런 경우에 우리가 정말로 계속해서 운이 없이 임의의 수 'a' 를 생성하게 되면 매번 우리는 '바보들'을 고를 것입니다 만일 여러분이 이것을 충분하게 이해했다면 그것을 정말로 잘 이해할 것입니다 그럼 지금 여기서 우리가 시도하는 숫자를 증가시켜서 테스트 하면 이것은 완벽하게 작동하는 것 처럼 보입니다 그리고 최악의 경우에는 이미 우리가 알고 있듯이 만일 우리의 알고리즘에 소수를 넣게 된다면 그것은 최대한으로 많이 작동할 것입니다 페르마의 소수 테스트는 특히 각 단계의 숫자가 입력의 크기에 따라서 결정되지 않기 때문에 Trial Division 방식보다 더 효율적입니다 그리고 그것이 핵심적인 특징입니다 우리가 반복 횟수만 지정해주고 나면 예전처럼 우리의 알고리즘이 백만번이고 천만번이고 반복하여 작동할 걱정을 하지 않아도 됩니다 즉 이것은 전형적으로 수학을 응용하였다는 것을 의미합니다 이렇게 누군가 발견한 패턴을 사용하는 것으로 우리는 막대한 양의 컴퓨터 계산량을 절약할 수 있습니다 그러나 이 시스템에서는 아주 작은 한 결점이 있어요 여러분이 한번 찾아보시겠어요?