Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Кездейсоқ болып көрінетін, бірақ шын мәнінде детерминистік, себептік процесс арқылы жасалған. Псевдокездейсоқ сандар тізбегі – бұл толыққанды детерминистік және қайталанатын процесспен құрылған, бірақ статистикалық тұрғыдан кездейсоқ болып көрінетін тізбек. Қарапайым тілмен айтқанда, мәселе мынада: адамдарға қолжетімді кездейсоқтықтың көптеген көздері (мысалы, ойыншық сүйектерді лақтыру) компьютерлік бағдарламаларға оңай қолжетімді емес физикалық процестерге негізделген.
Appearing random but actually being generated by a deterministic, causal process
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Simply put, the problem is that many of the sources of randomness available to humans (such as rolling dice) rely on physical processes not readily available to computer programs.
Өмірбаян
Кездейсоқ сандарды жасаудың көптеген қолданыстары бар, мысалы, кездейсоқ үлгі алу, Монте-Карло әдістері, үстел ойындары немесе құмар ойындары. Алайда, физикада гравитациялық үдеу сияқты көптеген процестер детерминистік болып табылады, яғни бірдей бастапқы нүктеден әрқашан бірдей нәтиже шығады. Радиоактивті ыдырау және кванттық өлшеулер – бұл ерекше жағдайлар, олар физиканың негізіндегі нағыз кездейсоқ процестер ретінде модельденеді. Бұл процестер кездейсоқ сандардың практикалық көзі болмағандықтан, псевдокездейсоқ сандар қолданылады, олар детерминистік процесс арқылы жасалған болса да, нағыз кездейсоқ тізбектей болжамсыз болуға тиіс. Көптеген қолданыстарда детерминистік процесс – псевдокездейсоқ сан генераторы деп аталатын компьютерлік алгоритм болып табылады, оған алдымен кездейсоқ тұқым деп аталатын сан берілуі керек. Бір тұқым әрқашан бірдей тізбекті тудыратындықтан, тұқымды жақсы таңдау және оны жасыру маңызды, әсіресе қауіпсіздік саласында, онда тізбектің болжамсыздығы маңызды рөл атқарады. Кейбір жағдайларда тізбектің болжамсыздығын дәлелдеу маңызды болғанда, радиоактивті ыдырау, станциялар арасындағы радиодан жиналған атмосфералық электромагниттік шу немесе пернелерді басу уақыты сияқты физикалық кездейсоқ сандар көздері қолданылған. Бұл сандарды алуға кеткен уақыт компромиске әкеледі: осы физикалық өлшемдердің кейбіреулерін псевдокездейсоқ сан генераторының тұқымы ретінде пайдалану.
The generation of random numbers has many uses, such as for random sampling, Monte Carlo methods, board games, or gambling. In physics, however, most processes, such as gravitational acceleration, are deterministic, meaning that they always produce the same outcome from the same starting point. Some notable exceptions are radioactive decay and quantum measurement, which are both modeled as being truly random processes in the underlying physics. Since these processes are not practical sources of random numbers, pseudorandom numbers are used, which ideally have the unpredictability of a truly random sequence, despite being generated by a deterministic process. In many applications, the deterministic process is a computer algorithm called a pseudorandom number generator, which must first be provided with a number called a random seed. Since the same seed will yield the same sequence every time, it is important that the seed be well chosen and kept hidden, especially in security applications, where the pattern's unpredictability is a critical feature. In some cases where it is important for the sequence to be demonstrably unpredictable, physical sources of random numbers have been used, such as radioactive decay, atmospheric electromagnetic noise harvested from a radio tuned between stations, or intermixed timings of keystrokes. The time investment needed to obtain these numbers leads to a compromise: using some of these physics readings as a seed for a pseudorandom number generator.
Тарих
Қазіргі заманғы компьютерлер пайда болмас бұрын, кездейсоқ сандарға мұқтаж зерттеушілер оларды түрлі жолдармен (құбиктер, карталар, рулетка дөңгелектері) жасаушы еді. Ал 1955 жылы осы нәтижелер «Миллион кездейсоқ сан, 100 000 қалыпты ауытқумен» деген атпен жарияланды.
Before modern computing, researchers requiring random numbers would either generate them through various means (dice, cards, roulette wheels, the results were eventually published in 1955 as A Million Random Digits with 100,000 Normal Deviates.
Есептеу күрделілігі
Теориялық компьютерлік ғылымда, егер берілген қарсыластар класының ешбір қарсыласы оны біркелкі үлестіруден едәуір артықшылықпен ажырата алмаса, онда үлестіру сол қарсыластар класына қарсы псевдорандомды болып саналады. Псевдорандомдық туралы осы ұғым есептеу күрделілігі теориясында зерттеледі және криптографияда қолданылады. Формальды түрде, S және T – шекті жиындар болсын, ал F = {f: S → T} – функциялар класы болсын. D үлестірімі S жиыны бойынша, F класына қарсы ε-псевдорандомды болады, егер F класындағы кез келген f функциясы үшін, D үлестірімінен алынған және S жиынындағы біркелкі үлестіруден алынған үлестірімдер арасындағы статистикалық қашықтық ε-дан аспаса. Типтік қолданыстарда F класы шектеулі ресурстармен есептеу моделін сипаттайды, ал зерттеушілер F класына қарсы белгілі қасиеттері бар D үлестірулерін құруға қызығушылық танытады. D үлестірімі көбінесе псевдорандомдық генератордың нәтижесі ретінде беріледі.
In theoretical computer science, a distribution is pseudorandom against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage. This notion of pseudorandomness is studied in computational complexity theory and has applications to cryptography. Formally, let S and T be finite sets and let F = {f: S → T} be a class of functions. A distribution D over S is ε pseudorandom against F if for every f in F, the statistical distance between the distributions and , where is sampled from D and is sampled from the uniform distribution on S, is at most ε. In typical applications, the class F describes a model of computation with bounded resources and one is interested in designing distributions D with certain properties that are pseudorandom against F. The distribution D is often specified as the output of a pseudorandom generator.