Генератор на случайни числа – Уикипедия

Генератор на случайни числа е изчислително или физическо устройство, предназначено да генерира поредица от числа или символи, в която липсва каквато и да е зависимост, т.е. да са случайни. Широко използвани са компютърно базирани системи за генериране на случайни числа. Въпреки че не постигат целта да са наистина случайни, те удовлетворяват някои статистически тестове за „случайност“ в смисъл, че генерираните числа нямат помежду си лесно забележима зависимост. Методи за генериране на случайни числа съществуват отдавна. Примери за това са хвърляне на зарове, хвърляне на монета (ези и тура), разбъркване на карти за игра и др.

Приложение[редактиране | редактиране на кода]

Генерирането на случайни числа намира приложение в хазарта, компютърните симулации, криптографията и други места, където е нужен непредвидим резултат. Използва се също при разработването на симулации чрез метода Монте Карло^[1], тъй като дебъгването се улеснява от възможността за възпроизвеждане на една и съща случайна редица отново при преповтаряне на началните условия.

Генерирането на случайни числа е важна и широко разпространена задача в компютърното програмиране. Числата генерирани от компютъра чрез някакъв предопределен процес, не могат по дефиниция да се нарекат случайни. Знаейки алгоритъма, по който се изчисляват резултатите, и чрез неколкократното му изпълнение, ние можем да предскажем какво ще бъде следващото число.^[2] Докато криптографията и някои изчислителни алгоритми изискват много висока степен на видимо случайни резултати, то много други операции изискват по-малка степен на случайност. Примери за това могат да бъдат приложения като „Случаен цитат за деня“ или начина по който се контролира противник от компютъра, в дадена компютърна игра. По-малко случайни резултати се използват при хеш-алгоритми и алгоритми за автоматизирано търсене и сортиране.

Някои проблеми, които на пръв поглед изглеждат подходящи за генериране на случаен елемент се оказва, че не са толкова прости. Пример е функцията „разбъркване“ на повечето музикални устройства, която избира привидно случайни музикални творби, но само изглежда случайна. Истински случайна система не би имала ограничението да избира неколкократно една и съща песен.

Случайни и псевдослучайни числа[редактиране | редактиране на кода]

Има два основни метода използвани за генерирането на случайни числа. Единият от тях измерва някой физичен феномен, който се счита, че е случаен и след това компенсира възможните отклонения по време на измерването. Примери за такива източници са измерванията на атмосферен шум, термичен шум и други външни електромагнитни и квантови явления. Космическото фоново лъчение или радиоактивния разпад например, измерени през кратък интервал от време представляват източник на природна ентропия^[3].

Скоростта с която ентропията може да бъде добита от естествени източници зависи от феномена, който се измерва. По тази причина източниците на естествените случайни резултати се разглеждат като скоростно ограничени, тъй като се изчаква добиването на достатъчно количество ентропия, която да отговори на изискванията.

Вторият метод за генериране на случайни числа е чрез използване на изчислителни алгоритми, които връщат като резултат дълги поредици от очевидно случайни числа, които всъщност са напълно определени от друга по-кратка начална стойност или ключ. По този начин една и съща последователност от числа може да бъде възпроизвеждана неограничен брой път, ако се знае началната стойност, която определя алгоритъма. Този тип генератор, често се нарича псевдослучаен генератор на числа.

Някои системи използват хибриден подход, при който, когато е възможно използват физическия метод за генериране на случайни числа, а ако не е възможно, използват софтуерно-базирани криптографски генератори на псевдослучайни числа (CSPRNGs). Вторият метод се използва, когато изискването за генериране на случайни резултати, надхвърля възможността за обработване и добиване на естествената ентропия. По този начин се избягва скоростното ограничение и блокирането на системата, когато обработването на резултатите не отговаря на търсенето.

Методи за генериране на случайни и псевдослучайни числа[редактиране | редактиране на кода]

Физически методи[редактиране | редактиране на кода]

Най-ранните методи за генериране на случайни числа, като зарове, монети, карти за игра и рулетки, се използват и днес предимно в хазартните игри, но са твърде тромави за приложения в статистиката и криптографията.

Някои физични явления, като топлинния шум в ценеровия диод изглежда, че са наистина случайни и могат да се използват, като основа на хардуерните генератори на случайни числа.

Изчислителни методи[редактиране | редактиране на кода]

Генераторите на псевдослучайни числа са алгоритми, които могат автоматично да създават дълги поредици от числа (дори и с милиони членове), които изглеждат случайни на хората, но всъщност са резултат от някаква математическа зависимост^[4]. Такава поредица рано или късно започва да се повтаря или изчисляването на следващия ѝ член надхвърля наличната памет на системата. Един от най – известните алгоритми е линейният конгруентен метод, който използва следната рекурентна формула:

${\displaystyle X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m}$

Максималният брой числа, които се получават по тази формула е равен на числото m. За да се избегнат конкретни неслучайни свойства на единичния линеен конгруентен генератор няколко такива случайни генератори работят паралелно с леко различни стойности на множителния коефициент и с един „главен“ генератор на случайни, който избира от няколко такива генератори.

Друг такъв метод е обикновения метод с „лист и химикалка“ или така нареченият метод на средните квадрати предложен от Джон фон Нойман. Въпреки неговата леснота на прилагане, резултатите са с лошо качество – обхваща кратък период и има сериозни слабости, като например получената поредица почти винаги клони към нула.

Повечето компютърни езици за програмиране съдържат функции или библиотечни методи, които предоставят генератори на случайни числа. В повечето случаи те са създадени, за да предоставят случаен байт, дума или число с плаваща запетая с равномерно разпределение между 0 и 1.

Качеството, в смисъл случайността на подобни библиотечни функции, варира широко от напълно предсказуем изход до криптографски сигурен такъв. Генераторът на случайни числа по подразбиране в много езици, включително Python, Ruby, R, IDL и PHP, е базиран на т. нар. алгоритъм „вихър на Мерсен“ (англ. Mersenne Twister, от името на френския математик Марѐн Мерсѐн) и не е достатъчно сигурен за криптографски цели, както е изрично посочено в документацията на езика. Такива библиотечни функции имат слаби статистически свойства и някои ще повторят поредица след само няколко десетки хиляди опита. Те обикновено се инициализират използвайки часовника за реално време на компютъра като основа, тъй като такъв часовник по принцип отмерва в милисекунди, което е отвъд пределите на човешката точност. Тези функции може и да предлагат достатъчен елемент на случайност за определени задачи (видеоигрите например), но са неподходящи там, където е необходим качествен такъв елемент, като например криптографски приложения, статистически и числов анализ.

По-качествени източници на случайни числа са на разположение в повечето операционни системи. Например /dev/random на различни BSD версии, Linux, Mac OS X, IRIX и Solaris или CryptGenRandom за Microsoft Windows. Повечето програмни езици, включително споменатите по-горе, осигуряват средства за достъп до тези източници с по-високо качество.

Генериране чрез разпределението на вероятностите[редактиране | редактиране на кода]

Съществуват няколко метода за генериране на случайни числа базирани на функцията на разпределение на вероятностите. Тези методи включват превръщането на равномерно разпределено случайно число по някакъв начин. Поради тази причина тези методи работят еднакво добре както за псевдослучайните, така и за действително случайните числа. Един от методите, така нареченият метод на инверсията, включва нарастването до площ по-голяма или равна на тази на случайното число (което би трябвало да е генерирано между 0 и 1 за съответните разпределения). Друг такъв метод е методът на „приемане-отхвърляне“, който представлява вземане на стойности за x и y и проверка дали разпределителната функция на x е по-голяма от стойността на y. Ако е – тогава стойността на x се приема, в противен случай се отхвърля и алгоритъмът опитва отново.

Генериране от човека[редактиране | редактиране на кода]

Генериране на случайни числа също може да се извършва и от хората, под формата на събиране на различни детайли от крайните потребители и използването им като източник на рандомизацията. Въпреки това, повечето проучвания установяват, че липсва пълна случайност, когато хора се опитват да произвеждат последователност от случайни цифри или букви например^[5]. Те могат да редуват едни и същи елементи твърде често и поради тази причина този подход не е широко разпространен.

Последваща обработка и статистически проверки[редактиране | редактиране на кода]

Дори при избиране на надежден източник на правдоподобни случайни числа, получаването на напълно независими такива изисква допълнително внимание. Често тези генератори се влияят от външни фактори и отчитането на отклоненията при настъпване на такива бъгове е трудно.

Понякога случайността на генерираните числа е обект на статистически тестове за да се провери, че създалият ги генератор работи коректно и след това минават последваща обработка за да се подобрят статистическите им свойства.

Обобщение[редактиране | редактиране на кода]

От казаното до момента, трябва да се има предвид, че няма такъв всеобхватен генератор на случайни числа, който да гарантира, че няма да има каквито и да е дефекти в работата си. Всеки софтуерен инженер трябва внимателно да избира какъв генератор на случайни числа да използва, като се запознае добре с недостатъците и положителните страни на всеки един такъв, и прецени какъв му трябва за неговата специфична нужда (дали иска да е бърз, „истински“ случаен, равномерен и т.н.). Поради това, че няма едно решение за всеки проблем, софтуерният инженер е нужно да е запознат с какви средства би могъл да предпази възможно по най-добър начин своя софтуерен продукт от бъдеща нежелана намеса в нормалната му работа, и да изготви нужните мерки за да предотврати „случайни“ събития, които могат да бъдат предвидени.^[6]

Вижте също[редактиране | редактиране на кода]

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

Външни препратки[редактиране | редактиране на кода]

• Документ на NAG

Източници[редактиране | редактиране на кода]

Тази страница частично или изцяло представлява превод на страницата Random_number_generation в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​