Жасанды сандар генераторы - Pseudorandom number generator

A жалған кездейсоқ сандар генераторы (PRNG), сондай-ақ а детерминирленген кездейсоқ бит генераторы (DRBG),^[1] болып табылады алгоритм қасиеттері реттіліктің қасиеттеріне жуық сандар тізбегін құру үшін кездейсоқ сандар. PRNG-дің бірізділігі шынымен емес кездейсоқ, өйткені ол PRNG деп аталатын бастапқы мәнмен толығымен анықталады тұқым (ол шынымен кездейсоқ мәндерді қамтуы мүмкін). Шынайы кездейсоқтыққа жақын тізбектерді қолдану арқылы жасауға болады аппараттық кездейсоқ сандар генераторлары, жалған кездейсоқ сан генераторлары санның пайда болу жылдамдығымен және олардың қайта жаңғыртылуымен практикада маңызды.^[2]

PRNG сияқты қосымшаларда орталық болып табылады модельдеу (мысалы Монте-Карло әдісі ), электрондық ойындар (мысалы. үшін процедуралық ұрпақ ), және криптография. Криптографиялық қосымшалар шығарылымды бұрынғы нәтижелерден болжауға болмайтындығын және басқаларын талап етеді өңделген алгоритмдер, қарапайым PRNG сызықтығын мұрагер етпейтіндер қажет.

Жақсы статистикалық қасиеттер PRNG шығарудың негізгі талабы болып табылады. Жалпы, PRNG-нің мақсатқа сай қолдану үшін кездейсоқтыққа жақын сандарды шығаратындығына сенімді болу үшін мұқият математикалық талдау қажет. Джон фон Нейман PRNG-ді шынымен кездейсоқ генератор ретінде қате түсіндіру туралы ескертті және «кездейсоқ цифрларды шығарудың арифметикалық әдістерін қарастыратын адам, әрине, күнәкар күйде» деп қалжыңдады.^[3]

Детерминирленген генераторлармен ықтимал мәселелер

Іс жүзінде көптеген жалпы PRNG-дің нәтижелері көрсетіледі артефактілер бұл олардың статистикалық заңдылықты анықтау сынақтарынан сүрінуіне әкеледі. Оларға мыналар жатады:

Кейбір тұқым жағдайлары үшін күтілгеннен қысқа кезеңдер (мұндай жағдайда тұқымдық жағдайларды «әлсіз» деп атауға болады);
Үлкен көлемде құрылған сандар үшін біркелкі таралудың болмауы;
Бірізді құндылықтардың өзара байланысы;
Шығару реттілігінің өлшемді үлестірімі нашар;
Белгілі бір шамалар пайда болатын арақашықтықтар кездейсоқ реттіліктің үлестірілімінен өзгеше бөлінеді.

Қате PRNG-де көрсетілген ақаулар байқалмайтыннан (және белгісіз) өте айқынға дейін. Мысал ретінде RANDU ондаған жылдар бойы қолданылған кездейсоқ сандар алгоритмі негізгі компьютерлер. Бұл өте ақаулы болды, бірақ оның жеткіліксіздігі ұзақ уақыт бойы анықталмады.

Көптеген салаларда ХХІ ғасырға дейінгі кездейсоқ іріктеуге негізделген ғылыми жұмыс Монте-Карло имитациялар немесе басқа жолдармен PRNG-ге сенім арту сапасыз PRNG-ді қолдану нәтижесінде сенімділіктен әлдеқайда аз болды.^[4] Қазіргі кезде де сақтықты талап етеді, бұл ескертуде көрсетілгендей Халықаралық статистикалық ғылым энциклопедиясы (2010).^[5]

Тасталуы керек кең қолданылатын генераторлардың тізімі [жақсы генераторлар тізіміне қарағанда] әлдеқайда көп. Бағдарламалық жасақтама жеткізушілеріне соқыр сеніммен қарамаңыз. Сіздің сүйікті бағдарламалық жасақтаманың әдепкі RNG-ін тексеріп, қажет болса оны ауыстыруға дайын болыңыз. Бұл соңғы ұсыныс соңғы 40 жыл ішінде қайта-қайта жасалған. Мүмкін, таңқаларлықтай, ол 40 жыл бұрынғыдай маңызды болып қала береді.

Көрнекілік ретінде кеңінен қолданылатын бағдарламалау тілін қарастырыңыз Java. 2017 жылғы жағдай бойынша^{[жаңарту]}, Java әлі де a-ға сүйенеді сызықтық конгруденциялы генератор (LCG) оның PRNG үшін,^[6]^[7] сапасы төмен - төменде қараңыз.

Үлкен проблемаларды болдырмауға және өте тез жұмыс істеуге мүмкіндік беретін танымал PRNG - бұл Мерсен Твистер (төменде талқыланған), ол 1998 жылы жарық көрді. Басқа да сапалы PRNG, есептеу және статистикалық көрсеткіштер тұрғысынан, осы күнге дейін және одан кейін жасалған; бұларды анықтауға болады Жалған кездейсоқ генераторлардың тізімі.

Сызықтық қайталануларға негізделген генераторлар

20 ғасырдың екінші жартысында PRNG үшін қолданылатын алгоритмдердің стандартты класы құрылды сызықтық конгруденциялы генераторлар. LCG сапасының жеткіліксіз екендігі белгілі болды, бірақ одан да жақсы әдістер қол жетімді болмады. Press et al. (2007) нәтижені осылай сипаттады: «Егер нәтижелері [LCG және басқа қатысты заттарға] байланысты күмән тудыратын барлық ғылыми жұмыстар кітапхана сөрелерінен жоғалып кетсе, әр сөреде сіздің жұдырығыңыздай үлкен алшақтық пайда болар еді».^[8]

Жалған кездейсоқ генераторларды салудағы үлкен жетістік - оған негізделген техниканы енгізу болды сызықтық қайталанулар екі элементті өрісте; осындай генераторлар байланысты сызықтық кері байланыс ауысымының регистрлері.

1997 жылғы өнертабыс Мерсен Твистер,^[9] атап айтқанда, бұрынғы генераторларға қатысты көптеген мәселелерден аулақ болды. Mersenne Twister 2 кезеңі бар^19 937−1 қайталау (≈4.3.)×10⁶⁰⁰¹), екендігі дәлелденді тең бөлінді 623 өлшемге дейін (32 биттік мәндер үшін), және оны енгізу кезінде басқа статистикалық негізделген генераторларға қарағанда жылдамырақ жұмыс істеді.

2003 жылы, Джордж Марсаглия отбасын таныстырды xorshift генераторлар,^[10] қайтадан сызықтық қайталануға негізделген. Мұндай генераторлар өте жылдам және сызықты емес жұмысымен бірге олар күшті статистикалық тексерулерден өтеді.^[11]^[12]^[13]

2006 жылы АЛЛА генераторлар отбасы дамыды.^[14] WELL генераторлары белгілі бір дәрежеде Mersenne Twister-дің сапасын жақсартады, ол өте кең күйге ие және нөлдік саны бар жай кеңістіктен өте баяу қалпына келеді.

Криптографиялық қауіпсіз псевдоорандалық сандар генераторлары

Жарамды PRNG криптографиялық қосымшалар а деп аталады криптографиялық қауіпсіз PRNG (CSPRNG). CSPRNG-ге қойылатын талап - тұқым туралы білмейтін қарсыласта тек қана болуы керек елеусіз артықшылығы генератордың шығу реттілігін кездейсоқ реттіліктен ажыратуда. Басқаша айтқанда, PRNG тек белгілі бір статистикалық тестілерден өтуі қажет болса, CSPRNG барлық статистикалық тестілерден өтуі керек көпмүшелік уақыт тұқым мөлшерінде. Бұл қасиеттің дәлелі қазіргі заманғы өнер деңгейінен тыс болса да есептеу күрделілігі теориясы, нақты дәлелдер келтірілуі мүмкін төмендету CSPRNG а проблема деп болжануда қиын, сияқты бүтін факторлау.^[15] Жалпы, алгоритмді CSPRNG ретінде сертификаттаудан бұрын бірнеше жыл қарау қажет болуы мүмкін.

CSPRNG кейбір сыныптарына келесілер кіреді:

ағын шифрлары
блоктық шифрлар жүгіру санауыш^[16] немесе шығыс кері байланыс режимі
Криптографиялық қауіпсіздігі үшін арнайы жасалған PRNG, мысалы Microsoft Келіңіздер Бағдарламалаудың криптографиялық интерфейсі функциясы CryptGenRandom, Yarrow алгоритмі (енгізілген Mac OS X және FreeBSD ), және Фортуна
бірнеше PRNG қарабайыр алгоритмдерін кез-келген анықталатын кездейсоқтықты жою мақсатымен біріктіруге тырысатын PRNG жиынтығы
математикалық қаттылық болжамдарына негізделген арнайы жобалар: мысалдарға мыналар жатады Micali-Schnorr генераторы,^[17] Naor-Reingold жалған кездейсоқ функциясы және Blum Blum Shub қауіпсіздіктің сенімді дәлелі болатын алгоритм (мұндай алгоритмдер дәстүрлі конструкциялармен салыстырғанда өте баяу және көптеген қосымшалар үшін практикалық емес)
жалпы PRNGs: криптографиялық қауіпсіз PRNG кез-келгенінен генералды түрде құрылуы мүмкін екендігі көрсетілген бір жақты функция,^[18] бұл жалпы құрылыс іс жүзінде өте баяу, сондықтан негізінен теориялық қызығушылық туындайды.

Болуы мүмкін екендігі көрсетілген NSA асимметрия енгізді артқы есік ішіне NIST сертификатталған жалған кездейсоқ сандар генераторы Dual_EC_DRBG.^[19]

PRNG алгоритмдерінің көпшілігі тізбекті құрайды біркелкі бөлінген бірнеше сынақтың кез-келгенімен. Бұл теория және практика үшін орталық сұрақ криптография, жоғары сапалы PRNG нәтижесін шынымен кездейсоқ реттіліктен ажыратудың қандай-да бір әдісі бар ма. Бұл параметрде ажыратқыш белгілі PRNG алгоритмі қолданылғанын (бірақ инициализацияланған күйде емес) немесе кездейсоқ алгоритмнің қолданылғанын біледі және екеуін ажырата білуі керек.^[20] PRNG-ді қолданатын көптеген криптографиялық алгоритмдер мен хаттамалардың қауіпсіздігі сәйкес PRNG-ді шынымен кездейсоқ реттілікті қолдануды ажырату мүмкін емес деген болжамға негізделген. Бұл тәуелділіктің қарапайым мысалдары ағын шифрлары, ол (көбінесе) жұмыс істейді эксклюзивті немесе - ашық мәтін PRNG шығаратын хабарлама, шығаратын шифрлықмәтін. Криптографиялық адекватты PRNG-ді жобалау өте қиын, өйткені олар қосымша критерийлерге сәйкес келуі керек. Оның кезеңінің мөлшері PRNG-дің криптографиялық жарамдылығының маңызды факторы болып табылады, бірақ жалғыз емес.

BSI бағалау критерийлері

Неміс Ақпараттық қауіпсіздік жөніндегі федералды бюро (Bundesamt für Sicherheit in der Informationstechnik, BSI) детерминирленген кездейсоқ сандар генераторларының сапасының төрт өлшемін белгіледі.^[21] Олар осында жинақталған:

K1 - кездейсоқ сандардың реттілігі бір-бірінен өзгеше болу ықтималдығы жоғары болуы керек.
K2 - сандар тізбегі көрсетілген статистикалық сынақтарға сәйкес «шынымен кездейсоқ» сандардан ерекшеленбейді. Тесттер: монобит тест (тізбектегі бірліктер мен нөлдердің тең сандары), покер тест (. арнайы данасы квадраттық тест ), жүгіреді тест (әр түрлі ұзындықтағы жүгіру жиілігін есептейді), ұзақ мерзімдер тест (кезектіліктің 20 000 битінде 34 немесе одан үлкен ұзындықтың бар-жоғын тексереді) - бастап BSI^[21] және NIST,^[22] және автокорреляция тест. Шын мәнінде, бұл талаптар биттер тізбегінің қаншалықты жақсы екендігіне тест болып табылады: нөлдер мен олардың теңдіктері бірдей; тізбегінен кейін n нөлдер (немесе бірліктер), келесі ықтималдықтың жартысы бар бір (немесе нөл); және кез-келген таңдалған тізбектегі кезектегі келесі элементтер (лер) туралы ақпарат жоқ.
K3 - шабуылдаушы (барлық практикалық мақсаттар үшін) кез-келген берілгендіктен, кезектегі кез-келген алдыңғы немесе болашақ мәндерді немесе генератордың ішкі күйін есептеуі немесе басқаша болжауы мүмкін болмауы керек.
K4 - барлық практикалық мақсаттар үшін шабуылдаушы генератордың ішкі күйін, кезектегі кез-келген алдыңғы сандарды немесе ішкі генератордың кез-келген күйін есептеуі немесе болжауы мүмкін болмауы керек.

Криптографиялық қосымшалар үшін тек K3 немесе K4 стандарттарына сәйкес келетін генераторлар ғана қабылданады.

Математикалық анықтама

Берілген

${ displaystyle P}$ - ықтималдықтың таралуы ${ displaystyle left ( mathbb {R}, { mathfrak {B}} right)}$ (қайда ${ displaystyle { mathfrak {B}}}$ стандарт болып табылады Борел қойды нақты сызықта)
${ displaystyle { mathfrak {F}}}$ - Borel жиынтығының бос емес жиынтығы ${ displaystyle { mathfrak {F}} subseteq { mathfrak {B}}}$ , мысалы. ${ displaystyle { mathfrak {F}} = left { left (- infty, t right]: t in mathbb {R} right }}$ . Егер ${ displaystyle { mathfrak {F}}}$ көрсетілмеген, ол да болуы мүмкін ${ displaystyle { mathfrak {B}}}$ немесе ${ displaystyle left { left (- infty, t right]: t in mathbb {R} right }}$ , контекстке байланысты.
${ displaystyle A subseteq mathbb {R}}$ - бос емес жиынтық (Borel жиынтығы міндетті емес). Жиі ${ displaystyle A}$ арасындағы жиынтық ${ displaystyle P}$ Келіңіздер қолдау және оның интерьер; мысалы, егер ${ displaystyle P}$ аралықта біркелкі үлестіру болып табылады ${ displaystyle left (0,1 right]}$ , ${ displaystyle A}$ мүмкін ${ displaystyle left (0,1 right]}$ . Егер ${ displaystyle A}$ көрсетілмеген, ол қолдаудың кейбір жиынтығы деп қабылданады ${ displaystyle P}$ және контекстке байланысты оның интерьерін қамтиды.

Біз функцияны атаймыз ${ displaystyle f: mathbb {N} _ {1} rightarrow mathbb {R}}$ (қайда ${ displaystyle mathbb {N} _ {1} = left {1,2,3, dots right }}$ натурал сандардың жиыны) а үшін жалған кездейсоқ сандар генераторы ${ displaystyle P}$ берілген ${ displaystyle { mathfrak {F}}}$ мәндерді қабылдау ${ displaystyle A}$ егер және егер болса

${ displaystyle f left ( mathbb {N} _ {1} right) subseteq A}$
${ displaystyle forall E in { mathfrak {F}} quad forall 0 < varepsilon in mathbb {R} quad N in mathbb {N} _ {1} quad forall бар N leq n in mathbb {N} _ {1}, quad left | { frac { # left {i in left {1,2, dots, n right } : f (i) in E right }} {n}} - P (E) right | < varepsilon}$

( ${ displaystyle #S}$ ақырлы жиынтықтағы элементтер санын білдіреді ${ displaystyle S}$ .)

Көрсетуге болады, егер ${ displaystyle f}$ - біркелкі үлестіруге арналған жалған кездейсоқ сандар генераторы ${ displaystyle сол жаққа (0,1 оңға)}$ және егер ${ displaystyle F}$ болып табылады CDF берілген ықтималдық үлестірімінің ${ displaystyle P}$ , содан кейін ${ displaystyle F ^ {*} circ f}$ үшін жалған кездейсоқ сандар генераторы болып табылады ${ displaystyle P}$ , қайда ${ displaystyle F ^ {*}: left (0,1 right) rightarrow mathbb {R}}$ процентилі болып табылады ${ displaystyle P}$ , яғни ${ displaystyle F ^ {*} (x): = inf left {t in mathbb {R}: x leq F (t) right }}$ . Ерікті үлестіруді интуитивті түрде стандартты біркелкі үлестірімді имитациялаудан модельдеуге болады.

Ерте тәсілдер

Ұсынған ертедегі компьютерлік PRNG Джон фон Нейман 1946 жылы, ретінде белгілі орта квадрат әдісі. Алгоритм келесідей: кез-келген санды алып, оны квадратқа бөліп, алынған санның ортаңғы цифрларын «кездейсоқ сан» ретінде алып тастаңыз, содан кейін сол санды келесі итерация үшін дән ретінде қолданыңыз. Мысалы, «1111» санын квадратқа бөлгенде «1234321» шығады, оны «01234321» деп жазуға болады, 8 таңбалы сан 4 таңбалы санның квадраты болады. Бұл «кездейсоқ» сан ретінде «2343» санын береді. Бұл процедураны қайталау келесі нәтиже ретінде «4896» береді және т.б. Фон Нейман 10 таңбалы сандарды қолданды, бірақ процесс бірдей болды.

«Орта квадрат» әдісінің проблемасы - барлық тізбектер ақыр соңында қайталанады, кейбіреулері өте тез, мысалы, «0000». Фон Нейман бұл туралы білген, бірақ ол бұл мақсатты өзінің мақсаттары үшін жеткілікті деп тапты және математикалық «түзетулер» қателерді жойғаннан гөрі оларды жасырады деп қорықты.

Фон Нейман аппараттық кездейсоқ сандардың генераторларын жарамсыз деп санады, өйткені егер олар шығарылған өнімді жазбаған болса, кейінірек оларды қателіктерге тексеру мүмкін болмады. Егер олар өз нәтижелерін жазған болса, олар компьютерлердің шектеулі жадын, сөйтіп компьютердің сандарды оқу және жазу қабілетін сарқып алар еді. Егер сандар карточкаларға жазылса, оларды жазуға және оқуға әлдеқайда көп уақыт кететін еді. Үстінде ENIAC ол қолданған компьютер, «орта квадрат» әдісі сандарды оқудан жүз есе жылдам жылдамдықпен шығарды перфокарталар.

Орташа квадрат әдісі содан бері неғұрлым жетік генераторлармен ығыстырылды.

Жақындағы жаңалық - орта квадратты а-мен біріктіру Вейл тізбегі. Бұл әдіс ұзақ мерзім ішінде сапалы өнім шығарады (қараңыз) Орташа алаң Weyl тізбегі PRNG ).

Біртекті емес генераторлар

Ықтималдықтың біркелкі емес үлестірімінен таңдалған сандарды a көмегімен жасауға болады біркелкі үлестіру PRNG және екі үлестірімді байланыстыратын функция.

Біріншіден, біреу керек жинақталған үлестіру функциясы ${ displaystyle F (b)}$ мақсатты тарату ${ displaystyle f (b)}$ :

{ displaystyle F (b) = int _ {- infty} ^ {b} f (b ') db'}

Ескертіп қой ${ displaystyle 0 = F (- infty) leq F (b) leq F ( infty) = 1}$ . Кездейсоқ санды қолдану c ықтималдық тығыздығы ретінде «өту» үшін біркелкі үлестіруден аламыз

{ displaystyle F (b) = c}

сондай-ақ

{ displaystyle b = F ^ {- 1} (c)}

- бұл үлестірімнен кездейсоқ таңдалған сан ${ displaystyle f (b)}$ .

Мысалы, кумулятивтік кері Гаусс таралуы ${ displaystyle operatorname {erf} ^ {- 1} (x)}$ кіріс ретінде диапазоны (0, 1) бар идеалды бірыңғай PRNG бар ${ displaystyle x}$ Гаусс үлестірімімен (тек оң) мәндер тізбегін шығарады; дегенмен

Практикалық сандық көріністерді қолданғанда үлестірімнің шексіз «құйрықтарын» ақырғы мәндерге дейін қысқарту керек.
Қайталап қайта есептеу ${ displaystyle operatorname {erf} ^ {- 1} (x)}$ сияқты құралдармен қысқартылуы керек алгоритм жылдам ұрпақ үшін.

Ұқсас пікірлер сияқты басқа біркелкі емес үлестірімдерді құруға қолданылады Рэли және Пуассон.

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Smid, Miles (шілде 2012). «Негізгі басқаруға арналған ұсыныс» (PDF). NIST Арнайы жарияланым 800-57. NIST. Алынған 19 тамыз 2013.
^ «Жалған кездейсоқ генераторлар». Хан академиясы. Алынған 2016-01-11.
^ Фон Нейман, Джон (1951). «Кездейсоқ сандарға байланысты қолданылатын әр түрлі әдістер» (PDF). Ұлттық стандарттар бюросы қолданбалы математика сериясы. 12: 36–38.
^ Press et al. (2007), 7 тарау
^ L'Ecuyer, Pierre (2010). «Бірыңғай кездейсоқ сандардың генераторлары». Ловрикте, Миодраг (ред.) Халықаралық статистикалық ғылым энциклопедиясы. Спрингер. б. 1629. ISBN 3-642-04897-8.
^ Кездейсоқ (Java Platform SE 8), Java Platform Standard Edition 8 Documentation.
^ Random.java кезінде OpenJDK.
^ Press et al. (2007) §7.1
^ Мацумото, Макото; Нишимура, Такуджи (1998). «Mersenne twister: 623 өлшемді тең бөлінген біртекті жалған кездейсоқ сандар генераторы» (PDF). Модельдеу және компьютерлік модельдеу бойынша ACM операциялары. ACM. 8 (1): 3–30. дои:10.1145/272991.272995.
^ Марсаглия, Джордж (шілде 2003). «Xorshift RNGs». Статистикалық бағдарламалық қамтамасыз ету журналы. 8 (14).
^ С.Вигна. «xorshift * / xorshift + генераторлары және PRNG атысы».
^ Vigna S. (2016), «Marsaglia's xorshift генераторларын эксперименттік зерттеу», Математикалық бағдарламалық жасақтамадағы ACM транзакциялары, 42; дои:10.1145/2845077.
^ Vigna S. (2017), «Marsaglia's xorshift генераторларын одан әрі талқылау», Есептеу және қолданбалы математика журналы, 315; дои:10.1016 / j.cam.2016.11.006.
^ Паннетон, Франсуа; Л'Экуйер, Пьер; Мацумото, Макото (2006). «2 модуль бойынша сызықтық қайталануларға негізделген ұзақ мерзімді генераторлар жетілдірілген» (PDF). Математикалық бағдарламалық жасақтамадағы ACM транзакциялары. 32 (1): 1–16. дои:10.1145/1132973.1132974.
^ Ән. RSA-ға криптаналитикалық шабуылдар. Springer, 2007. б. 73. ISBN 978-0-387-48741-0.
^ Нильс Фергюсон, Брюс Шнайер, Тадаёси Кохно (2010). «Криптографиялық инженерия: жобалау принциптері және практикалық қолдану, 9.4 тарау: генератор» (PDF).CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
^ Клаус Поммеренинг (2016). «IV.4 Perfect кездейсоқ генераторлар». Криптология. uni-mainz.de. Алынған 2017-11-12. MICALI-SCHNORR генераторы
^ Пасс, Рафаэль. «Дәріс 11: Голдрейх-Левин теоремасы» (PDF). COM S 687 Криптографияға кіріспе. Алынған 20 шілде 2016.
^ Мэттью Грин. «Dual_EC_DRBG көптеген кемшіліктері».
^ Катц, Джонатан; Ехуда, Линделл (2014). Қазіргі заманғы криптографияға кіріспе. CRC баспасөз. б. 70.
^ ^а ^б Шиндлер, Вернер (2 желтоқсан 1999). «Детерминирленген кездейсоқ сандарды генераторлар үшін функционалдық сыныптар және бағалау әдістемесі» (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. 5-11 бет. Алынған 19 тамыз 2013.
^ «Криптографиялық модульдерге қойылатын қауіпсіздік талаптары». FIPS. NIST. 1994-01-11. б. 4.11.1 Қуатты сынау. Архивтелген түпнұсқа 2013 жылғы 27 мамырда. Алынған 19 тамыз 2013.

Библиография

Баркер Э., Келси Дж., Детерминирленген кездейсоқ бит генераторларын қолдану арқылы кездейсоқ санды құруға арналған ұсыныс, NIST SP800-90A, қаңтар 2012 ж
Брент Р.П., «Ауысым мен хорды қолданатын кездейсоқ сандардың кейбір ұзақ мерзімді генераторлары», ANZIAM журналы, 2007; 48: C188-C202
Gentle J.E. (2003), Кездейсоқ сандардың генерациясы және Монте-Карло әдістері, Springer.
Hörmann W., Leydold J., Derflinger G. (2004, 2011), Автоматты біркелкі емес кездейсоқ өзгермелі генерация, Springer-Verlag.
Кнут Д.Е.. Компьютерлік бағдарламалау өнері, 2 том: Жартылай алгоритмдер, Үшінші басылым. Аддисон-Уэсли, 1997 ж. ISBN 0-201-89684-2. 3-тарау. [Кездейсоқ емес статистикалық тестілерді кеңінен қамту]
Люби М., Псевдокандрость және криптографиялық қосымшалар, Принстон Унив Пресс, 1996 ж. ISBN 9780691025469
фон Нейман Дж., «Кездейсоқ цифрларға байланысты қолданылатын әртүрлі тәсілдер», А.С. Үй иесі, Г.Е. Форсайт және Х.Х. Жермонд, редакция., Монте-Карло әдісі, Қолданбалы математиканың ұлттық стандарттар бюросы, 12 (Вашингтон, Колумбия окр.: АҚШ үкіметінің баспа кеңсесі, 1951): 36–38.
Петерсон, Айварс (1997). Кездейсоқ Джунгли: математикалық сафари. Нью-Йорк: Джон Вили және ұлдары. ISBN 0-471-16449-6.
W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Сандық рецепттер (Кембридж университетінің баспасы ).
Виега Дж., "Бағдарламалық жасақтамада кездейсоқ санды генерациялау «Жыл сайынғы компьютерлік қауіпсіздікті қолдану жөніндегі 19 жылдық конференция, 2003 ж. желтоқсан.

Сыртқы сілтемелер

Сынақ U01: Тегін, заманауи (GPL ) C ++ Кездейсоқ сандар жиынтығы.
DieHarder: Тегін (GPL ) C Кездейсоқ сандар жиынтығы.
"Кездейсоқ сандарды құру «(in.) ендірілген жүйелер ) Эрик Унер (2004)
"Linux кездейсоқ сандар генераторын талдау «Зви Гуттерманның, Бенни Пинкас, және Тзачи Рейнман (2006)
"Жалған кездейсоқ генераторлар «Парикшит Гопалан, Рагу Мека, Омер Рейнгольд, Лука Тревизан, және Салил Вадхан (Microsoft Research, 2012)
rand () зиянды деп саналады қосулы YouTube Стефан Лававейдж (Microsoft, 2013)
Wsphynx қарапайым онлайн кездейсоқ сандар генераторы. Кездейсоқ санды Javascript псевдодан кездейсоқ сандар генераторлары (PRNGs) жасайды

[1] Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Smid, Miles (шілде 2012). «Негізгі басқаруға арналған ұсыныс» (PDF). NIST Арнайы жарияланым 800-57. NIST. Алынған 19 тамыз 2013.

[2] «Жалған кездейсоқ генераторлар». Хан академиясы. Алынған 2016-01-11.

[3] Фон Нейман, Джон (1951). «Кездейсоқ сандарға байланысты қолданылатын әр түрлі әдістер» (PDF). Ұлттық стандарттар бюросы қолданбалы математика сериясы. 12: 36–38.

[4] Press et al. (2007), 7 тарау

[5] L'Ecuyer, Pierre (2010). «Бірыңғай кездейсоқ сандардың генераторлары». Ловрикте, Миодраг (ред.) Халықаралық статистикалық ғылым энциклопедиясы. Спрингер. б. 1629. ISBN 3-642-04897-8.

[6] Кездейсоқ (Java Platform SE 8), Java Platform Standard Edition 8 Documentation.

[7] Random.java кезінде OpenJDK.

[8] Press et al. (2007) §7.1

[9] Мацумото, Макото; Нишимура, Такуджи (1998). «Mersenne twister: 623 өлшемді тең бөлінген біртекті жалған кездейсоқ сандар генераторы» (PDF). Модельдеу және компьютерлік модельдеу бойынша ACM операциялары. ACM. 8 (1): 3–30. дои:10.1145/272991.272995.

[10] Марсаглия, Джордж (шілде 2003). «Xorshift RNGs». Статистикалық бағдарламалық қамтамасыз ету журналы. 8 (14).

[11] С.Вигна. «xorshift * / xorshift + генераторлары және PRNG атысы».

[12] Vigna S. (2016), «Marsaglia's xorshift генераторларын эксперименттік зерттеу», Математикалық бағдарламалық жасақтамадағы ACM транзакциялары, 42; дои:10.1145/2845077.

[13] Vigna S. (2017), «Marsaglia's xorshift генераторларын одан әрі талқылау», Есептеу және қолданбалы математика журналы, 315; дои:10.1016 / j.cam.2016.11.006.

[14] Паннетон, Франсуа; Л'Экуйер, Пьер; Мацумото, Макото (2006). «2 модуль бойынша сызықтық қайталануларға негізделген ұзақ мерзімді генераторлар жетілдірілген» (PDF). Математикалық бағдарламалық жасақтамадағы ACM транзакциялары. 32 (1): 1–16. дои:10.1145/1132973.1132974.

[15] Ән. RSA-ға криптаналитикалық шабуылдар. Springer, 2007. б. 73. ISBN 978-0-387-48741-0.

[16] Нильс Фергюсон, Брюс Шнайер, Тадаёси Кохно (2010). «Криптографиялық инженерия: жобалау принциптері және практикалық қолдану, 9.4 тарау: генератор» (PDF).CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)

[17] Клаус Поммеренинг (2016). «IV.4 Perfect кездейсоқ генераторлар». Криптология. uni-mainz.de. Алынған 2017-11-12. MICALI-SCHNORR генераторы

[GoldreichLevinNotes-18] Пасс, Рафаэль. «Дәріс 11: Голдрейх-Левин теоремасы» (PDF). COM S 687 Криптографияға кіріспе. Алынған 20 шілде 2016.

[19] Мэттью Грин. «Dual_EC_DRBG көптеген кемшіліктері».

[20] Катц, Джонатан; Ехуда, Линделл (2014). Қазіргі заманғы криптографияға кіріспе. CRC баспасөз. б. 70.

[bsi_ais20-21] а ^б Шиндлер, Вернер (2 желтоқсан 1999). «Детерминирленген кездейсоқ сандарды генераторлар үшін функционалдық сыныптар және бағалау әдістемесі» (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. 5-11 бет. Алынған 19 тамыз 2013.

[22] «Криптографиялық модульдерге қойылатын қауіпсіздік талаптары». FIPS. NIST. 1994-01-11. б. 4.11.1 Қуатты сынау. Архивтелген түпнұсқа 2013 жылғы 27 мамырда. Алынған 19 тамыз 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]