Random Number Generation

Въведение

Генерирането на случайни числа, посредством изчислителни “генератори”, е една много важна задача, която всеки програмист трябва да отдаде нужното и задълбочено внимание. В повечето случаи на един софтуерен инженер му се налага да използва под една или друга форма някакъв набор от случайни стойности във своите програми, поради ред на брой причини. Според мен най-важната от тях е тази, да бъде осигурен един надежден и сигурен код, който да защити потребителя и собственика на софтуера от външна или вътрешна нежелана (понякога с цел зловредна и/ или злонамерена) намеса в нормалната изначално заложена работа на продукта.

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

Важно е да бъде отбелязано, че Генераторите на Случайни Числа (от тук нататък, ще бъдат записвани за кратко като ГСЧ) играят важна роля в математиката като цяло, криптографията,  хазартните игри (електронни казино игри)[1], а също и в много други области където е нужно за дадена симулация на събитие (да речем симулация чрез метода “Монте Карло”), алгоритми на човешкият геном и др. да бъдат получени числа максимално/ истински близки до абсолютната “случайност”, за да бъдат пресъздадени изброените по напълно правдоподобен и сигурен за дадената дейност начин.

Повечето случайни числа използвани в изчислителната техника като цяло, не са считани за наистина случайни, защото са създадени чрез Псевдо-ГСЧ. ПГСЧ представляват алгоритми от детерминиран тип (алгоритми, които винаги при един и същ подаден вход връщат един и същ резултат, като преминават през една и съща поредица от състояния.), и са единственият тип случайни числа, които могат да бъдат алгоритмично създадени без използването на външен източник на ентропия [3] (~ средната “случайност” на едно случайно число или колко случайни са измерваните характеристики на източника на ентропия) – като например термален шум и/ или други природни явления. Трябва да се знае, че алгоритъм само от детерминиран тип не може да създаде истински случайни числа, поради факта, че изчисленията му се базират на “познати” данни.

Следният списък е на едни от по-известните и широко използвани алгоритми за ПГСЧ [1]:

Какво представлява генерирането на случайно число чрез ГСЧ?

Математически погледнато ГСЧ могат да бъдат дефинирани като структура (S; μ; f; U; g), където S представлява краен набор от състояния, μ е разпределената вероятност (дистрибуция) на S използвана за избирането на началното състояние (или сито) s0, в отношението f : S -> S е преходна функция, U  представлява краен набор от изходни символи, а пък g : S -> U е изходящата функция.

Състоянието еволюира спрямо броят проявления sn = f(sn), където n ≥ 1. Изходът при стъпка n, е un = g(sn)∈U. Всъщност un, представлява така наречените случайни числа генерирани от ГСЧ. Понеже S е крайно, генераторът ще се върне в един бъдещ момент към състояние, което вече е посетил (и.к. si+j = si за някой i ≥ 0 и j > 0). Тогава, sn+j = sn и un+j = un за всяко n ≥ i.

Най-малкото j > 0 за което това се случи се нарича дължина на периода ρ. То не може да надвишава кардиналостта на S. А по конкретно, ако b бита биват използвани, за да представят състоянието, тогава ρ ≤ 2b. Добрите ГСЧ са направени, така че тяхната дължина на периода да бъде възможно най-близка до тази горна граница. [2]

А защо да не потърсим случайност/ случайни числа сред физическите устройства?

Защо да използваме компютърен алгоритъм от детерминиран тип, вместо наистина, истински случаен механизъм за генериране на случайни числа? Обяснението е просто, само ако си представим, че за даден експеримент или дадено софтуерно приложение (финансово или друго), ни се налага хиляда или милиони (милиарди) пъти да се допитаме до “магическата” топка с числа, зарчета или нещо подобно за истинско случайно генериране на число – не мислите ли, че би било по-удобно и практично да се извика дадена системна функционалност, която да извърши тази дейност даден/ краен брой пъти. И все пак, опити са били правени да се конструират ГСЧ от физически устройства, като “звукови/ шумови” диоди, броячи на гама-лъчи и т.н. , но те си остават до голяма степен непрактични и ненадеждни, защото са “тежки” (трудни за интегриране) и бавни от към извършване на своята дейност, а също и като цяло твърдението, че последователните числа генерирани от тях са уникални и равномерно разпределени е невярно. Един добър подход за излизане от само детерминираните алгоритми, е да комбинираме резултата от един добре направен ГСЧ с природен/ физически (физичен) “шум”. [2]

Следният списък е на компании които произвеждат (Истински) Физически/ Хардуерни ГСЧ [1]:

  • Araneus Alea
  • ComScire
  • Entropy Key
  • Fox-IT Fox RandomCard
  • ID Quantique
  • Intel 810/815/840/845G chipsets
  • Intel RdRand instruction
  • LETech
  • Protego
  • TRNG98
  • true-random.com
  • VIA Padlock engine
  • Westphal Electronic

Изброените по-горе компании от сравнително скоро или им предстои да представят/ продават продуктите си като такива. По отделно или заедно те са  предимно отделни хардуерни компоненти (а има и също такива които могат да бъдат системно интегрирани), които твърдят, че са Истински ГСЧ, като ползват комбинация от един или повече физично генерирани “шумове”, след което някой от тях “пресяват” резултата чрез набор от ПГСЧ за по-добра дистрибуция. Търсената ентропия при ИГСЧ е от порядъка на 0.99 бита/ бит – по смисъла на хвърлена монета, където ако имаме правилно/ честно хвърлена монета , шанса да се падне ези или тура е 50/50 или иначе казано ентропията е 1, единица.

Обобщение и Примери

Един лош пример за зле замислен и изпълнен алгоритъм за ГСЧ е RANDU, създаден през 1960, той е от типа на Линейно “Съгласувани” Генератори – Linear Congruential Generator. На картинката по-долу може да се види защо наистина това е един недобър алгоритъм:

Фигура 1 – Триизмерна равнина с 100, 000 стойности, в интервала (0, 1), генерирани чрез RANDU. Всяка точка представлява 3 последователни псевдо – случайни стойности. Ясно се вижда как стойностите попадат в 15 двуизмерни равнини.

Друг пример за лош подбор на ГСЧ идва от компанията Netscape, годината е 1996, и става дума за слабост в браузъра им, която е била “злонамерено” открита. SSL (Secure Socket Protocol) протокола (за сигурно предаване на данни през интернет, където се използва криптиране на предаваните данни), използван в ранните версии на браузъра, е представлявал ГСЧ посредством три неизвестни стойности за “пресяване”/ seeding – като това са били: часът, Уникалният Номер на процеса, и УН на родителският процес. Така зададените “неизвестни” стойности са всъщност относително предвидими, като дават на ГСЧ една доста незначителна ентропия. Проблема е бил първо забелязан от учен работещ в ЦЕРН, а по-късно открит в самия код чрез обратно-пресъздаване от двама докторанти по Компютърни Науки на Университета Бъркли, Калифорния [5].

Един добър пример за добре написан ПСГЧ алгоритъм би бил Mrg32k3a. Същия се използва доста сериозно в много значителни софтуерни приложения като MatLab, хардуерни архитектури като тези на Intel, а също и при графична обработка на данни като при Nvidia Cuda. В конкретният случай става дума за Обектно-ориентиран пакет за ГСЧ, реализиран в C [7]. Той представлява Комбиниран Много-Рекурсивен ГСЧ, (осъществен в 64-битова архитектура с плаваща десетична запетая) като има дължина на периода ρ ≈ 2191. “Ситото”/ The Seeding на ГСЧ и състоянието на потока по време на която и да е стъпка е 6-измерен вектор с 32-битови числа [6].

От всичко казаното до момента, трябва да имаме в предвид, че няма такъв всеобхватен ГСЧ, който да гарантира, че не ще има каквито и да е дефекти в работата си. Всеки софтуерният инженер трябва да е много внимателен как подбира такива ГСЧ, като предварително направи разчет дали иска сам да напише такъв и/ или да използва готов – като се запознае добре с недостатъците и положителните страни на всеки един такъв, и прецени какъв му трябва за неговата специфична нужда (дали иска да е бърз, “истински” случаен, равномерен и т.н.). Поради това, че няма едно решение за всеки проблем, софтуерният инженер е нужно да е запознат с какви средства той/ тя биха могли да предпазят възможно по най-добър начин своят софтуерен продукт от бъдеща нежелана намеса в нормалната му работа, и да изготви нужните мерки за да предотврати “случайни” събития, които могат да бъдат предвидени.

При все вече казаното за ПГСЧ, съществуват такива, като следните, които имат една доста добра теоретична обоснованост, обстойно са били разгледани най-различни сценарии за тяхната коректност в работата, а и да не забравяме, че те са също и лесни за употреба: Mersenne Тwister на Matsumoto и Nishimura (1998), комбинираните Мулти – Рекурсивни Генератори (ГСЧ) на L’Ecuyer (1999a), комбинираните Линейно “Съгласувани” Генератори (ГСЧ) на L’Ecuyer and Andres (1997), и комбинираните Tausworthe генератори на L’Ecuyer (1999b). [2]

Цитирани Източници

  1. List of random number generators. (2012, March 16). In Wikipedia, The Free Encyclopedia. Retrieved 21:52, March 17, 2012, from http://en.wikipedia.org/w/index.php?title=List_of_random_number_generators&oldid=482170050
  2. Random Numbers. Pierre L’Ecuyer, Universite de Montreal, Montreal, Quebec, Canadahttp://www.iro.umontreal.ca/~lecuyer/myftp/papers/ensbs.pdf
  3. Random Number Generation. Author: Chris Lomont – http://www.lomont.org http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf
  4. RANDU. (2012, February 17). In Wikipedia, The Free Encyclopedia. Retrieved 23:40, March 18, 2012, from http://en.wikipedia.org/w/index.php?title=RANDU&oldid=477436760
  5. Randomness and the Netscape Browser. http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html
  6. http://www.iro.umontreal.ca/~lecuyer/myftp/streams00/c2010/RngStream.pdf
  7. http://www.iro.umontreal.ca/~lecuyer/myftp/streams00/c2010/
Advertisements
Comments
2 Responses to “Random Number Generation”
  1. Hello.This article was extremely remarkable, particularly because I was browsing for thoughts on this topic last Thursday.

    • technobg says:

      I am glad you liked it! It is not a complete overview of the topic, but I consider it to provide some good insight in it, along with the information from the referenced sources. Unfortunately the article is in Bulgarian, not a widely popular and known language in the world :). I do plan a translation in plain English, in the near future ( when I have some free time 🙂 ).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  • Blog Stats

    • 318 hits
%d bloggers like this: