Генератори на псевдослучайни числа

(забавна музика) (шумолене на листа) Когато наблюдаваме физическия свят, навсякъде откриваме случайни изменения. Можем да генерираме същински случайни числа като измерим случайните изменения, познати като "шум". Когато измерим този шум, т.е. като вземем "извадка", можем да получим числа. Например, ако измерим електрическия ток на статична телевизия с времето, ще генерираме напълно случайна последователност. Можем да визуализираме тази случайна последователност, като нарисуваме път, който сменя посоката си според всяко число, познато като случайна походка. Забележи липсата на схема във всеки мащаб. Във всяка точка от тази последователност следващото движение е непредвидимо. Случайните процеси се наричат "недетерминистични", тъй като е невъзможно да се определят предварително. Машините, от друга страна, са детерминистични. Техните операции са предвидими и повторяеми. През 1946 г. Джон фон Нюман се занимава с изчисления за армията; особено с разработката на водородна бомба. Той използва компютъра ENIAC, за да планира повтаряеми изчислителни приближения на процесите, свързани с ядреното делене. Това изисква бърз достъп до случайно генерирани числа, които могат да се повтарят при нужда. ENIAC има много ограничена вътрешна памет; съхранението на дълги случайни последователности не било възможно. Затова Нюман разработва алгоритъм, който симулира механично разбъркването на случайности по следния начин: Първо се избира напълно случайно число, наречено "зародиш" (seed). Това число може да се получи от измерване на шума или времето в милисекунди. След това зародишът се задава като вход на просто изчисление. Умножава се по себе си и след това се извежда средата на този резултат. Този резултат се използва като следващ зародиш и процесът се повтаря колкото пъти е нужно. Този метод е известен като "метод на средните квадрати" и е само един от многото генератори на псевдослучайни числа. Случайността на последователността зависи само от случайността на първия зародиш. Един и същи зародиш, една и съща последователност. Каква е разликата между случайно генерирани и псевдослучайно генерирани последователности? Да представим всяка последователност като случайна пътека. Изглеждат подобни, докато не се ускорят. Псевдослучайната накрая ще започне да се повтаря. Когато алгоритъмът достигне до зародиша, който вече е използвал, цикълът се повтаря. Дължината преди повторението на псевдослучайната последователност се нарича "период". Периодът е строго ограничен от дължината на първия зародиш. Например, ако използваме двуцифрен зародиш, алгоритъмът може да даде най-много 100 числа преди да повтори зародиша и цикъла. Трицифрен зародиш дава над 1000 числа преди да повтори цикъла, а 4-цифрен зародиш може да даде 10 000 числа преди повторението. Ако използваме достатъчно голям зародиш, последователността може да достигне до трилиони и трилиони цифри преди да се повтори. Затова разликата в ключа е важна. Когато генерираш псевдослучайни числа, има много последователности, които не могат да се появят. Например, Алис генерира напълно случайна последователност от 20 отмествания, еквивалентна на еднаква селекция от купчина с всички възможни последователности от отмествания. Купчината съдържа 26 на степен 20 страници, което е астрономически размер. Ако сме до тази купчина и насочим фенер нагоре човекът, който е най-горе, ще види светлината чак след около 200 000 000 години. Сравни това с генерирането на 20-цифрена псевдослучайна последователност с 4-цифрен случаен зародиш. Това е еквивалентно на еднаква селекция от 10 000 възможни начални зародиши, което значи, че може да генерира само 10 000 различни последователности, което е ужасно малка част от всички възможни последователности. Когато минем от случайни към псевдослучайни отмествания, намаляваме множеството на ключовете до много, много по-малко множество на зародишите. За да не можем да различим пседослучайна последователност от случайна последователност, за един компютър ще бъде непрактично да провери всички зародиши и да види дали съвпадат. Това води до важно разграничаване в компютърните науки това какво е възможно и това какво е възможно за разумна единица време. Използваме същата логика, когато купуваме ключалка за колело. Знаем, че всеки може да опита всички възможни комбинации, докато намери вярната и отвори ключалката. Но това ще отнеме дни. Затова смятаме, че ключалката е сигурна за 8 часа. С псевдослучайни генератори сигурността нараства с дължината на зародиша. Ако на най-мощния компютър биха му трябвали стотици години, за да провери всички зародиши, тогава можем да приемем, че на практика е сигурно, вместо идеално сигурно. Тъй като компютрите стават по-бързи, размерът на зародиша трябва да нарасне. Псевдослучайността позволява на Алис и Боб да не се налага да споделят изцяло случайната си последователност от отмествания предварително. Вместо това, те споделят относително кратък случаен зародиш и го използват за получаването на една и съща случайно изглеждаща последователност, когато се наложи. Но какво се случва, ако не се срещнат, за да споделят този случаен зародиш?