랜덤 알고리즘이란?

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