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