Кіріспе
Кездейсоқ сандар тізбегінің жуық шамасын шығаратын алгоритм. Псевдокездейсоқ сандар генераторы (PRNG), сондай-ақ детерминистік кездейсоқ бит генераторы (DRBG) деп аталады, – бұл кездейсоқ сандар тізбектерінің қасиеттеріне ұқсас қасиеттері бар сандар тізбегін жасауға арналған алгоритм. PRNG жасаған тізбек шынайы кездейсоқ емес, өйткені ол PRNG тұқымы деп аталатын бастапқы мәнмен толық анықталады (оған шынайы кездейсоқ мәндер де кіруі мүмкін). Шын мәнінде кездейсоқ сандарға жақын тізбектерді аппараттық кездейсоқ сандар генераторларын қолдану арқылы жасауға болады, бірақ псевдокездейсоқ сандар генераторлары сандарды жасау жылдамдығы және қайталанатындығы тұрғысынан практикалық маңызға ие. PRNG-лер симуляциялар (мысалы, Монте-Карло әдісі), электрондық ойындар (мысалы, процедуралық генерация) және криптография сияқты қолданыстарда маңызды рөл атқарады. Криптографиялық қолданыстар үшін шығыс бұрынғы шығыстардан болжауға келмейтін болуы керек, сондықтан қарапайым PRNG-лердің сызықтығын мұра етпейтін күрделірек алгоритмдер қажет. PRNG шығысы үшін жақсы статистикалық қасиеттер – басты талап. Жалпы, PRNG мақсаттағы қолдануға жеткілікті жақын сандарды жасайтынына сенімді болу үшін мұқият математикалық талдау қажет. Джон фон Нейман PRNG-ді шынайы кездейсоқ генератор ретінде қате түсінуге қатысты ескертіп, әзілдеп: "Арифметикалық әдістермен кездейсоқ цифрларды жасауды ойлаған адам, әрине, күнәде" деді.
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e. g. for the Monte Carlo method), electronic games (e. g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not inherit the linearity of simpler PRNGs, are needed. Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use. John von Neumann cautioned about the misinterpretation of a PRNG as a truly random generator, joking that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
Сызықтық қайталануларға негізделген генераторлар
XX ғасырдың екінші жартысында PRNG үшін қолданылатын стандартты алгоритмдер класы сызықтық конгруенциялық генераторлардан тұрды. LCG-нің сапасы жеткіліксіз екені белгілі болғанмен, жақсырақ әдістер қолжетімді болған жоқ. Пресс және авторлар (2007) бұл мәселені былай сипаттады: «Егер [LCG және оған ұқсас] салдарынан нәтижелері күмәнді болып саналатын барлық ғылыми еңбектер кітапхана сөрелерінен жоғалып кетсе, әр сөреде сіздің жұмырығыңыздың көлемімен шамалас үлкен бос орын қалар еді». Псевдорандомдық генераторларды құрастырудағы маңызды қадам – екі элементтік өрістегі сызықтық рекурсияларға негізделген техникаларды енгізу болды; мұндай генераторлар сызықтық кері байланыс тізбектік тіркегіштерімен байланысты. 1997 жылы ойлап табылган Мерсенн Твистері, бұрынғы генераторлардың көптеген кемшіліктерінен сақтады. Мерсенн Твистері 219 937 − 1 итерациядан тұратын кезеңге ие (≈ 4.3), 623 өлшемде (32 биттік мәндер үшін) тең таралуы дәлелденді және енгізілген кезде басқа статистикалық тұрғыдан негізделген генераторлардан жылдам жұмыс істеді. 2003 жылы Джордж Марсалья xorshift генераторларының отбасын ұсынды, ол да сызықтық рекурсияға негізделген. Мұндай генераторлар өте жылдам және бейсызықтық операциялармен үйлестірілгенде, күшті статистикалық тесттерден өтеді. 2006 жылы WELL генераторларының отбасы әзірленді. WELL генераторлары кейбір жағынан Мерсенн Твистерінің сапасын жақсартады, оның күй кеңістігі тым үлкен және нөлдердің көп саны бар күй кеңістіктерінен жаңарту өте баяу жүреді.
Есептік көрсеткіштің бағалау критерийлері
Германияның Ақпараттық қауіпсіздік жөніндегі федералды басқармасы (Bundesamt für Sicherheit in der Informationstechnik, BSI) детерминистік кездейсоқ сан генераторларының сапасына қатысты төрт критерий белгіледі. Олар төменде жинақталған:
K1 – Генерацияланған кездейсоқ сандар тізбектерінің бір-бірінен едәуір айырмашылыққа ие болуы керек. K2 – Сандар тізбегі белгіленген статистикалық тесттерге сәйкес, «шынайы кездейсоқ» сандардан ажыратуға болмайды. Тесттер: монобиттік тест (тізбектегі бірліктер мен нөлдердің саны тең), покерлік тест (хи-квадраттық тесттің ерекше жағдайы), жүгіру тесті (әртүрлі ұзындықтағы тізбектердің жиілігін есептейді), ұзақ жүгіру тесті (20 000 биттен тұратын тізбекте 34 немесе одан ұзын тізбектердің болуын тексереді) – BSI және автокорреляциялық тест. Аталған талаптардың мәні – биттік тізбек қаншалықты жақсы: нөлдер мен бірліктерді тең пропорцияда қамтиды; n нөлдің (немесе бірліктің) тізбесінен кейін келесі бит жартылай ықтималдықпен бір (немесе нөл) болады; және кез келген таңдалған кіші тізбек тізбектегі келесі элемент туралы ешқандай ақпаратты қамтамайды. K3 – Шабуылдаушыға (практикалық тұрғыдан алғанда) кез келген берілген кіші тізбек бойынша тізбектегі кез келген бұрынғы немесе келешек мәндерді, сондай-ақ генератордың ішкі күйін есептеу немесе болжау мүмкін болмауы керек. K4 – Шабуылдаушы үшін генератордың ішкі күйінен тізбектегі кез келген бұрынғы сандарды немесе кез келген бұрынғы ішкі генератор күйлерін есептеу немесе болжау мүмкін болмауы керек. Криптографиялық қолданыстар үшін тек K3 немесе K4 стандарттарына сай келетін генераторлар ғана қабылданады.
Алғашқы тәсілдер
1946 жылы Джон фон Нейман ұсынған алғашқы компьютерлік PRNG ортаңғы квадрат әдісі деп аталады. Алгоритм мынадай: кез келген санды алып, оны квадраттап, нәтижедегі санның ортаңғы цифрларын "кездейсоқ сан" ретінде бөліп алыңыз, содан кейін осы санды келесі итерацияның бастамасы ретінде пайдаланыңыз. Мысалы, "1111" санын квадраттағанда "1234321" шығады, оны "01234321" деп жазуға болады, бұл 4 таңбалы санның квадраты болып табылатын 8 таңбалы сан. Бұл "2343" деген "кездейсоқ" санды береді. Бұл процедураны қайталағанда келесі нәтиже ретінде "4896" шығады, және т.б. Фон Нейман 10 таңбалы сандарды қолданған, бірақ процесс сол күйінде қалды. "Ортаңғы квадрат" әдісінің бір кемшілігі – барлық тізбектер ерте не кеш қайталанады, кейбіреулері өте жылдам, мысалы "0000". Фон Нейман мұны білген, бірақ ол бұл тәсілді өзінің мақсаттары үшін жеткілікті деп санады және математикалық "түзетулер" қателерді жоюдың орнына жасырады деп қорқыды. Фон Нейман аппараттық кездейсоқ сандар генераторларын қолайсыз деп тапты, себебі егер олар шығарылған нәтижені жазбаса, оларды кейін қателерге тексеру мүмкін болмас еді. Егер сандар карталарға жазылса, оларды жазу мен оқу әлдеқайда ұзаққа созылар еді. Ол қолданған ENIAC компьютерінде "ортаңғы квадрат" әдісі перфокартадан оқылған сандарға қарағанда жүз есе жылдам сандарды жасады. Ортаңғы квадрат әдісі содан бері күрделірек генераторлармен алмастырылды. Соңғы жаңалық – ортаңғы квадратты Вейль тізбегімен біріктіру. Бұл әдіс ұзақ кезеңде жоғары сапалы нәтижелер береді (ортаңғы квадрат әдісін қараңыз).