Среда, 17.07.2019, 02:36
Приветствую Вас ПОСТОРОННИЙ | RSS
Welcome to the world of Studio GRELIKTIKON
Главная
Регистрация
Вход
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
"ИНФОРМАЦИОННЫЙ ЦЕНТР" » "ХРАМ" » Уроки » Генератор псевдослучайных чисел
Генератор псевдослучайных чисел
fear-ogameДата: Четверг, 03.09.2009, 13:02 | Сообщение # 1
Admin
Группа: Администраторы
Сообщений: 3341
Награды: 3
Статус: Offline
Генератор псевдослучайных чисел

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL (англ.): «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».


" Не тот велик, кто ни когда не падал,
а тот велик, кто падал и вставал"
 
fear-ogameДата: Четверг, 03.09.2009, 13:04 | Сообщение # 2
Admin
Группа: Администраторы
Сообщений: 3341
Награды: 3
Статус: Offline
Детерминированные ГПСЧ

Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые свойства случайных чисел. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений».

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 2n/2, где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2n. Если ГПСЧ может сходиться к слишком коротким циклам, такой ГПСЧ становится предсказуемым и является непригодным.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

* Слишком короткий период/периоды.
* Последовательные значения не являются независимыми.
* Некоторые биты «менее случайны», чем другие.
* Неравномерное одномерное распределение.
* Обратимость.

В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим, что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, linear feedback shift registers, generalized feedback shift registers.

Из современных ГПСЧ широкое распространение получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937-1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью вихря Мерсенна, как неслучайную. Это делает вихрь Мерсенна неподходящим для криптографии.


" Не тот велик, кто ни когда не падал,
а тот велик, кто падал и вставал"
 
fear-ogameДата: Четверг, 03.09.2009, 13:07 | Сообщение # 3
Admin
Группа: Администраторы
Сообщений: 3341
Награды: 3
Статус: Offline
ГПСЧ с источником энтропии или ГСЧ

Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).

Почти все крупные производители микрочипов поставляют аппаратные ГСЧ с различными источниками энтропии, используя различные методы для их очистки от неизбежной предсказуемости. Однако на данный момент скорость сбора случайных чисел всеми существующими микрочипами (несколько тысяч бит в секунду) не соответствует быстродействию современных процессоров.

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. До появления возможности считывать значения счётчика тактов, сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ до сих пор используют традиционные (устаревшие) методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow, или взаимодействия между потоками, как, например, в Java secure random.


" Не тот велик, кто ни когда не падал,
а тот велик, кто падал и вставал"
 
fear-ogameДата: Четверг, 03.09.2009, 13:10 | Сообщение # 4
Admin
Группа: Администраторы
Сообщений: 3341
Награды: 3
Статус: Offline
Читать далее

http://ru.wikipedia.org/wiki/PRNG


" Не тот велик, кто ни когда не падал,
а тот велик, кто падал и вставал"
 
fear-ogameДата: Четверг, 03.09.2009, 14:09 | Сообщение # 5
Admin
Группа: Администраторы
Сообщений: 3341
Награды: 3
Статус: Offline
Скачать генератор на русском языке можно здесь

http://www.1001soft.com/soft/generator_sluchainyh_chisel-12965.html

http://download.ru/products/generator-chisel?category_id=122&order=2


" Не тот велик, кто ни когда не падал,
а тот велик, кто падал и вставал"
 
"ИНФОРМАЦИОННЫЙ ЦЕНТР" » "ХРАМ" » Уроки » Генератор псевдослучайных чисел
  • Страница 1 из 1
  • 1
Поиск:


Copyright MyCorp © 2019