현재 시간:0:00전체 재생 길이:5:06
0 에너지 포인트
동영상 대본
첫째로, input을 N으로 하는 무작위적 알고리즘들의 새로운 타입들을 위한 개념을 만들어 봅시다. 만약 N이 prime (소수의, 최고의, 순수한)이라면, 알고리즘은 100% 무조건 prime을 output으로 가질 것입니다. 절대로 composite이 나오지 않을 것입니다. 하지만 만약 N이 composite (합성의)이라면, 그 것을 prime이라고 하는 아주 작은 실수 E의 확률이 존재할 것입니다. 그리고 반대로, 1에서 그 실수확률을 제외한 정확히 composite이라고 하는 확률이 존재 할 것입니다. 간단하게 생각해 봅시다. 전체 정수 범위 중에서 일부, 한 숫자를 잡아내어 그 수를 정수 N이라고 합니다. 우리는 우리의기계에 N을 집어 넣습니다. 이전에, 우리의 나누기 기계에서 우리는 1부터 N의 제곱까지 모든 수를 반복했고 그 숫자가 N을 나누는지 테스트 했습니다. 아주 좋게, 우리는 prime들만 체크하면 되기 때문에 시간을 절약할 수 있었습니다. 만약, 그렇죠, A가 N을 나눈다면 우리는 N이 합성수임을 알 수 있습니다. 왜냐하면 우리는 합성수임을 증명해주는 것을 찾았기 때문입니다. 만약 아니라면, 우리는 확신하지 못하겠죠. 따라서 우리는 다시 돌아가서 A를 증분하고 다시 테스트 해볼것 입니다. 우리가 모든 가능한 테스트를 다 해봤을 때 만약 나누는 수를 찾지 못한다면, 우리는 N이 소수라고 말 할 수 있습니다. 이제, 천천히 시작해 봅시다. 우리가 몇개의 무작위 정수들을 고르고 무작위적이라고 생각되는 몇개의 가분성 테스트를 하면 어떻게 될 까요? 우리는 어떤 수 N이 합성수라면, 반드시 나누는 수가 흩어져 있을 것이라는 것을 알고 있습니다. 최소한 하나는 가지고 있겠죠. 어떤 합성수들은 많은 나눗수를 가지고 있습니다. 어쨌든, 어떤 정수 A를 무작위적으로 뽑아봅시다. 1에서 N의 제곱 사이에 있는 정수로요. 됬습니다. 그리고 나서 A가 N을 나누는지 확인해 봅시다. 전 처럼, 만약 A가 N을 나누면, 우리는 확실하게 N이 합성수임을 알 수 있습니다. 증거를 찾았기 때문이죠. 만약 아니라면, 우리는 N이 소수일 수도 있다는 것 빼고는 많이 알 수는 없습니다. 그리고 확실하게 하기 위해서, 우리는 더 몇개의 무작위적 A를 만들어서 테스트를 할 것입니다. 아마 100 또는 1000번의 반복 후에는 테스팅을 멈추고, 약간의 확신을 가지고 "아마 N은 소수일 거야" 라고 말 할 것입니다. 99.9%라고 하죠. 이것은 조건부 확률의 예와 비슷합니다. 가장 간단한 버전으로, 만약 우리가 동전이 확률이 1/2인 공정한 동전인지 또는 둘 다 얼굴이 있는 동전인지 확인하는 경우가 있습니다. 이 경우에는, 숫자가 있는 면들을 찾는 것이 나눗수를 찾는 것과 같을 것입니다. 확률이 1/2인 동전을 증명해주기 때문입니다. 얼굴이 있는 부분이 나오는 것은 다시 동전을 던져서 반복하도록 하는 경우입니다. 이 때, 5번 얼굴이 나오고 나면 우리는 90% 이상 확신을 하게 되고 멈춘 다음, "우리는 동전의 양면이 얼굴이라고 생각한다" 라고 할 것입니다. 여기에 제가 만든 우리의 지난 나누셈 테스트와 이 새로운 무작위 나누셈 테스트를 비교하는 프로그램이 있습니다. 저는 특별하게 Dino를 사용하는 프로그램인 나누는 스피드 리더를 사용했습니다. 링크는 프로그램의 앞부분에 남겨 뒀습니다. 시작에 앞서, 테스트 할 변수들을 확인해 보세요. 이 숫자들은 무작위적인 추측 숫자들입니다. 3처럼 작은 것에서 부터 시작할 것입니다. 만약 input이 소수라면, 이런 작은 수의 input으로도, 무작위 나눗셈 알고리즘은 항상 output을 소수로 할 것임을 기억하세요. 만약 input이 합성수라면, 무작위 나눗셈이 실수를 해서 소수라고 틀리게 인식 할 수도 있습니다. 하지만, 점점 시도하는 숫자를 크게 함으로써 이 문제를 해결 할 수 있습니다. 그렇게 하면 실수의 확률을 줄여나 갈 수 있기 때문입니다. 이제 점점 output들이 일치하는 것이 보입니다. input을 크게 할 수록, 실수 (틀리게 인식하는 것)의 확률이 줄어듭니다. 무작위 테스트의 input도 따라서 증가시킬 필요가 있습니다. 그렇게 하면 output들이 더 아주 잘 일치합니다. 거의 결과가 똑같습니다. input을 아주 크게하면, 정확하게 하기위해서 무작위 테스트를 수천번 해야합니다. 즉, 실제로 필요한 단계의 수를 더 짧게 만들지 못하게 됩니다. 우리의 이전 나눗셈 방법이 더 나아보입니다. 왜냐하면 무작위 나눗셈 테스트의 에러(실수, 틀릴) 확률이 매우 높지만 우리의 나눗셈은 답에 가깝기 때문입니다. 이전 것이 맞는 것이죠. 따라서 우리는 다른 테스트가 필요합니다. 우리는 그 숫자가 합성수 인지 아닌지 증명하는데 쓰이는 계산이 빠른 방정식이 필요합니다. 그리고 그 식은 input으로 정수 N뿐만 아니라 무작위 정수 N을 받아들일 수 있고, 같은 방법으로 무작위 테스트를 할 수 있어야합니다.