현재 시간:0:00전체 재생 길이:9:23
0 에너지 포인트
동영상 대본
새로운 정보를 입수했습니다; NASA에 의하면, 우리의 우주 탐사선에 난수 발생기를 하나 달 계획이랍니다. 한가지 더 덛붙였는데요, 우리의 알고리즘이 실생활에서 문제없이 작동해야 한답니다. 무언가가 실생활에서 작동해야 한다는 것은, 항상 오류의 가능성이 있다는 뜻입니다; 단지 우리가 무시해도 될 정도로 가능성이 작은 것 뿐인데요, 이것이 약간 이상하게 들린다면, 실제 물리적인 세계에서는 확실한 것은 없습니다; 항상 오차와 오류의 범위가 있죠, 예를 들어, 어떠한 칩 패키징에는 극소량의 방사성 물질이 들어 있는데요, 이들이 붕괴할 때 알파 입자를 방출합니다; 이 입자들은 메모리의 비트를 뒤집을 수 있는데요, 이는 메모리 속 정보를 바꿀 수 있습니다. 더욱 흥미로운 점은, 태양, 우주에서 나오는 방사능 역시 소프트웨어에 오류를 일으킬 수 있다는 것입니다; 오류의 가능성을 완전히 없앨 수는 없죠. 그래서 저는 NASA에게 물어봅니다; '어느 정도의 오차까지가 허용되느냐?' 그들이 대답하지요; 우리는 이 오류가 생길 가능성이 로또 1등을 두 번 연속해서 당첨될 가능성보다 낮기만 하면 됩니다.' 라고 대답했지요. 로또를 두 번 연속해서 당첨되는 것의 확률은, 6*10^-14입니다; 안전하기 해두기 위해서, 우리의 오차를 10^-15으로 설정해 둡시다. 충분히 안전합니다; 우리는 오류를 볼 가능성은 거의 업지요. 이 프로그램을 수백만번 돌려도 문제 없습니다. 이제 저의 질문은요, 난수의 사용이 이 소수 구별 시험과 같은 선택 알고리즘의 작동을 더 빠르게 할 수 있을까요? 이는 약간 깊은 질문이기 때문에, 한 발짝 물러서고 큰 그림을 봅시다. 1부터 N까지의 정수의 집합이 있습니다; 이것이 우리의 모든 수의 집합이라고 생각합니다. 우리는 어느 집합이든 두 가지 경우로 나타낼 수 있습니다; 선택을 동반하는 문제에서는 이 집합을 두 종류로 나눌 수 있습니다. 예를 들어, N이 100 미만의 수이면, 100 미만의 모든 정수에 대하여 '예'라고 대답할 것입니다. 이렇게 하나의 집합이 있고요, 나머지는 '아니오'라고 답하겠죠, 이들은 그 자체로 다른 집합입니다. 그러면, 이제 이를 통해서 소수를 구별하는 것에 주의를 기울입시다. 이상적으로, 우리는 소수만 해당하며 합성수는 해당하지 않는 몇 가지의 간단한 규칙들을 찾고 싶은데요, 우리가 소수들의 위치를 알려주는 간단한 패턴 같은 것을 알고 있더라면, 소수들만입니다, 그럼 숫자 N이 있을 때 N이 그 패턴을 따르는지 보기만 하면 됩니다. 문제는, 소수에만 해당하며 합성수에만 해당하거나, 합성수에만 해당하며 소수에는 해당하지 않는 이러한 조건을 충족시키는 패턴을 아직 찾지 못했다는 것입니다. 그러나, 우리는 합성수를 구별하기 위한 몇 가지 쉽고 빠른 방법을 알고 있죠. 예를 들어, 어느 간단한 기준으로 짝수인지를 판별할 수 있습니다; 모든 짝수는 2로 나누어지지요. 우리는 1의 자리 숫자만 봐도 이를 판단할 수 있기 때문에 이는 매우 빠릅니다; 숫자 N이 얼마나 커지든간에, 문제는 어려워지지 않습니다; 1의 자리 숫자만 보면 됩니다. 이는 다른 말로 'low order bit'이라고도 부릅니다. 준치채셨겠지만, 우리는 이 짝수 판별 시험을 원시적인 합성수 시험으로 활용할 수 있습니다. 이를 이용해, 우리의 정수 N을 이 알고리즘에 넣으면, 이 알고리즘은 이 수가 짝수인지 판별할 것입니다. 이 수가 짝수이며 2보다 크면, 이 수가 합성수라는 것을 100% 확신할 수 있습니다. 증명할 수 있으니까요 두 수를 합성수의 목격자로 생각해보세요. 하지만 확실치 못할 때는 모든 소수가 홀수 있때는 또는 9나 15와 같은 많은 소수 중의 하나일 수 있습니다. 이 홀수의 소수는 받아들여질 수 없는 시험을 만듭니다. 명확히 하기 위해, 이것을 그려보죠. N이 있다고 합시다. N은 소수 또는 합성수가 될 수 있습니다. N이 소수라면 우리의 알고리즘은 100퍼센트 소수라고 말 할 것입니다. 소수는 2보다 큰 짝수가 없기 때문입니다. 소수가 나오면 절대 합성수라 얘기하지 않습니다. 그러나, 만일 N이 합성수라면 우리의 알고리즘은 50%가 합성수, 50%가 소수라고 말할 것입니다. 이것은 만일 우리 알고리즘이 합성수를 결과물로 내놓으면 합성수 목격을 증거로 발견할 것입니다. 그러나 우리 알고리즘이 소수를 결과물로 내놓는다면 엄청난 에러가 발생할 수 있다는 것을 알고 있죠. 지금까지, 이 커다랗고 받아들이지 어려운 계산의 반복으로 인한 에러에 대해 다뤄보고 있습니다. 우리 기계의 Flow를 그려봅시다. N을 주면, 이 기계는 일련의 나누기 테스크를 수행합니다. A가 이라는 시작점에서부터 A 나누기 N 이 가능한 지 물어봅니다. N을 나눌 수 없다면 , 그때 이 구역을 모두 없애 버릴 수 있습니다. 다음 질문을 물어봅니다. N이 3으로 나뉬니까? 만일 아니라면 전 섹션을 다 없애버립니다. N 나누기 5, 7, 등등을 합니까? 서로소인 관계를 주의합시다. 가능한 모든 합성수를 채우는 이제 예라는 대답을 하면 N이 합성수라른 것이 증명된 것입니다. A는 이 시점에서 증명입니다. N이 알고리즘에서 합성수를 결과물로 내는 것을 멈추게 합니다. 그렇지 않으면 가능한 모든 합성수를 다 써버릴 때까지 계속 돌려야 합니다. N의 제곱근을 만날 때까지요. 우리가 아는 한, 합성수 N은 N의 제곱근과 같거나 적은 인수를 가져야만 한다는 것을 기억하세요. 이것은 우리 알고리즘에 마지막 질문으로 유도합니다. 만일 증명이 안된다면, A가 N의 제곱근보다 크다면 증명이 되고 소수를 멈춰야 합니다. 알고리즘에서 2개 exit가 있었죠. 두 패스는 N이 소수거나 합성수 둘 중 하나라는 확실성의 증명을 나타냅니다. N이 소수일 때, 가능한 모두 약수를 써봐야 합니다. 기본적으로 모두 제외시키고 N 이 소수라는 증명을 이 전략의 문제는 최소 A값이 시작되는 소수 2에서부터 N의 제곱근의 값까지 사이클을 돌게 된다는 겁니다. N의 값이 커지면, 소수값도 따라 커집니다. 너무나 많은 반복이 일어나서 최악의 경우는 알고리즘에 한개의 소수만이 제공되는 경우입니다. 큰 그림을 보면서 N이 소수일 때 그것이 제공하는 증명을 봅시다. 우리가 필요치 않는 것은 아무도 우리가 그것을 증명해야 한다고 말하지 않았죠. 우리는 99.9999 가 되면 되는 겁니다. 59%의 정확성으로요. 우리 알고리즘에 사용되는 합성수 테스트에 대해 생각해 볼 필요가 있습니다. 명심하세요. 가장 빠른 나눗셈 시도방법은 소수성 테스트입니다. 6K 같은 소수 패턴을 사용하는 아니면 6K 플러스 또는 마이너스 원을 구성하는 모든 소수 소수만을 골라 사용하는 겁니다. 시간을 절약하기 위해 합성수는 제거시키고 이런 테스트는 합성수 테스트가 될 수도 있음을 명심하세요. 다시 말하자면 주어진 정수N은 6k 플러스 또는 마이너스 1의 구성이라는 겁니다. 아마 소수라고 할 수 있겠죠. 그러나 이 패턴을 따르는 많은 합성수가 여전히 존재합니다. 소수만을 포함하는 것이 아니죠. 모든 소수와 어떤 합성수 우리는 이 기타의 합성수를 취약점으로 생각합니다. 이 취약점이 에러 소스이지요. 이제 뒤집어서 N이 6k 플러스 또는 마이너스 1 의 형식이 아니라면 100%의 확신성으로 가지고 말할 수 있습니다. 합성수라고, 따라서 취약점은 에러의 근원이 되는 소수 입니다. 그러나 이 경우는 받아들여지지 않습니다. 무시할 만한 에러가 아닙니다. 더 큰 가능성이 있습니다. 이 공간을 줄여들게 만드는 합성수 테스팅 절차에 대해 새로이 정의를 해야 합니다. 에러가 무시해되 되는 기회로 만들어야 합니다. 즉, 어떻게 정수에 대한 에러를 줄여야 하는지 다시 살펴봐야 한다는 얘기입니다. 이제 아래에 우리의 아이디어를 포스트 해야 합니다 어떤 종류의 테스트를 수행해야 하는지를 고려하면서요. 또한 더 중요하게는 어떻게 임의의 숫자 제러네이터가 우리를 실제로 도와줄 수 있는지를 고려하면서요.