Старый взгляд на новые вещи
Эта статья не
даёт ответов - она лишь ставит вопросы. Здесь вы не найдёте инструкций для
выполнения - лишь указано направление. Нет уверенности, что вам вообще нужно её
читать.
" Мы
никогда не понимаем, какие сокровища перед нами. Знаешь почему? Потому что люди
вообще не верят в сокровища." Пауло Коэльо "Алхимик"
Оглянитесь
вокруг и вы поймёте, что миром правят случайности - они везде и всюду: от шума
в радиоприёмнике, до игры в орлянку и карт Таро, от русской рулетки и до ...
генерирования паролей. И ведь не известно, что более опасно.
Просто
удивительно насколько вся наша цивилизация (от крупного IT-специалиста, до
простого крестьянина) зависит от разного рода случайностей. А что самое
забавное (и таинственное) мы сами ставим себя в зависимость от каких-то
генераторов случайных чисел (ГСЧ)(random number generator). Причём к огромному
сожалению отнюдь не все ГСЧ являются действительно случайными. Взгляните хотя
бы на популярную функцию rand() из стандартной библиотеки stdlib.h
- её обманчивое поведение подробно рассматривается в статье "Укрощение rand() и random()". На
первый взгляд звучит очень забавно, что на случайные числа даже накладывают
ГОСТ-ы.
Как же вообще
получают эти замечательные числа? Существуют следующие способы получения случайных чисел:
1. Аппаратный способ. Можно использовать специальные приставки -
генераторы(датчики) случайных чисел. Этот способ не требует дополнительных
вычислительных операций ЭВМ по выработке случайных чисел, а необходима только
операция обращения ко внешнему устройству(датчику). В качестве физических
эффектов лежащих в основе таких генераторов могут быть использованы шумы в
электронных и полупроводниковых приборах(обусловлены следующим: тепловыми
флуктуациями, случайными вариациями числа частиц в электронных потоках,
хаотическим перемагничиванием доменов в ферромагнитных сердечниках), явление
распада радиоактивных элементов. 2.
Табличный способ. Случайные числа, оформленные в виде таблицы, помещаются во
внешнюю или оперативную память ЭВМ. Запас чисел ограничен. Эффективно
использовать только для сравнительно небольших таблиц, т.к. массив занимает
некоторый объём оперативной памяти! 3.
Алгоритмический способ. Формирование случайных (вернее - псевдослучайных) чисел
с помощью специальных алгоритмов. На генерацию псевдослучайных чисел
затрачивается машинное время.
Ниже приведены
примеры алгоритмического получения случайных чисел: Одной из исторически первых
процедур получения псевдослучайных чисел была процедура, называемая метод
серединных квадратов. Пусть имеется 2n-разрядное число, меньшее 1.
Возведём его в квадрат, а затем отберём средние 2n-разрядов, которые и
будут являться очередным числом псевдослучйной последовательности. Пример: x0=0.2152
x0^2=0.04631104
x1=0.6311
x1^2=0.39828721
x2=0.8287
...
Главный
недостаток этого метода - наличие корреляции между числами последовательности,
а иногда случайность может отсутствовать вовсе. Пример: x0=0.4500
x0^2=0.20250000
x1=0.2500
x1^2=0.06250000
x2=0.2500
...
Другой широко
применяемый тип генераторов случайных чисел -это так называемые конгруэнтные
генераторы. Для генерации используется следующая рекуррентная
последовательность: X(n+1)=a*X(n)+c*(mod
M). a
называется мультипликатором, c - инкрементом, M - модулем. mod -
это остаток от деления (основание системы счисления).
На основании
такого генератора работает уже упоминавшаяся двуликая функция rand().
Пожалуй пора
взглянуть на эти интересные числа. Давайте рассмотрим следующую последовательность
чисел:
8628034825
3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502
8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823
3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273
7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305
4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179
3105118548 0744623799 6274956735 1885752724 8912279381 8301194912 9833673362
4406566430 8602139494 6395224737 1907021798 6094370277 0539217176 2931767523
8467481846 7669405132 0005681271 4526356082 7785771342 7577896091 7363717872
1468440901 2249534301 4654958537 1050792279 6892589235 4201995611 2129021960
Как по-вашему
является ли она случайной? Кто-то может дать положительный ответ. Кто-то,
возможно чувствуя подвох, ответит отрицательно. По-настоящему мудро поступит
тот, кто не станет отвечать, усомнившись в корректности вопроса. Дело в том
(только не слишком удивляйтесь), что эта последовательность относится к числу
ПИ(PI), то есть, точнее говоря, это последователность чисел с 81-го по 720-й
знак после запятой числа ПИ. Так можно ли назвать эти числа случайными? Ниже
даётся ответ на этот вопрос:
Thus the successive digits of PI are as
determinate as any numbers can be, yet a block of a thousand of them might
serve quite well as random numbers for agricultural experiments, not because
they are random but because they are probably uncorrelated with the
peculiarities of a particular set of plots. Supplementation by
"chance" thus means (apart from minor, special requirements)
supplementation by taking effects (or variety) from a system whose behaviour
is uncorrelated with that of the main system. An example was given in S.12/15.
Thus if a chance variable were required, yesterday's price of a gold-share
might be suitable if the main system under study was a rat in a maze, but it
would not be suitable if the main system were a portion of the
financial-economic system.)
(Ashby W. R. An
introduction to CYBERNETICS) Для тех, кто не очень силён в английском, или у
кого переводчика нет :) дам небольшое пояснение: " последовательность
десятичных знаков числа ПИ являются определёнными(детерминированными), но блок
из тысячи знаков мог бы служить, как случайные числа, весьма хорошо, для
сельскохозяйственных экспериментов, не потому, что они случайны, а потому, что
они вероятно не коррелированы со специфическими особенностями земельных
участков. ..."
А теперь
давайте поглядим какие же средства для генерации "случайных" чисел
предоставляет любимая ОС Linux.
Загляните в директорию /dev/ и там вы сможете увидеть два
удивительных устройства, а именно /dev/random и /dev/urandom, которые
являются специальными устройствами, предоставляющими доступ к средствам
генерирования случайных чисел, встроенным в ядро. Давайте посмотрим, что выдают
эти устройства. Сделать это несложно. Воспользуемся утилитой od
(параметры -t
x1 говорят, чтобы утилита выдавала содержимое файла в
шестнадцатеричном формате. Дополнительную информацию по этой утилите можете
получить по команде man
od ).
$ od -t x1 /dev/random 0000000 cc fe 69
8b ce 70 18 1c da de 62 9e f4 3f 3b 9a 0000020 f2 b0 16 9c ab 5c 5f 35 7f 5d
d1 75 00 9b ce 16 0000040 4f af b0 6b 4e 52 50 32 b1 0c 36 70 e9 f2 5d b6
0000060 5d 7c 2d 28 23 d7 83 d3 38 a5 17 98 05 3d 06 dd 0000100 93 60 b4 d7
84 9f ce 07 ec 6a 4d e8 32 2b 2b 04
$ od -t x1 /dev/urandom 0000000 9d f8 32
64 9e 8e f0 26 0d 1e c4 f5 bb 99 37 f0 0000020 9a c1 37 8a 02 2d 78 81 64 d8
eb 6c 11 23 19 5b 0000040 10 e1 7d 3b 30 28 02 97 a9 57 c4 27 2c 4e 4f ef
0000060 ea 7a 4e a7 c1 d6 95 96 0a 99 f0 d4 cc 59 84 94 0000100 dd f6 85 df
e9 5a 37 53 1c 04 b7 ba f9 3a 8f 35
Как видите оба
устройства выдают случайные числа. На примере пока непонятно, чем же отличаются
файлы /dev/random
и /dev/urandom
друг от друга. Когда же вы запустите утилиту и немного подождёте, то увидете,
что /dev/urandom
не прекращает выдавать числа, тогда как /dev/random вскоре
перестанет это делать(вывод новых чисел прекратится), но как только вы
пошевелите мышкой или нажмёте клавиши на клавиатуре, как устройство выдаёт
очередную порцию чисел(согласитесь очень напоминает усердное нажатие разных
клавиш при генерировании ключа PGP). То
есть существенное отличие между этими устройствами состоит в том, что /dev/random
создаёт только случайные байты, которые получаются от внешнего источника хаоса
- пользователя !! Но запас случайных чисел в ядре ограничен и если читать
большое количество байт из файла(и не производить никаких пользовательских
действий), то система заблокирует операцию чтения. Ну а /dev/urandom
возвращает столько байт, сколько надо, т.е. когда запас случайных чисел в ядре
заканчивается, то за дело принимается генератор случайных чисел. Таким образом random
более предпочтителен для генерирования ключей доступа и прочих данных, к
которым предъявляется требования повышенной случайности , так как urandom
выдаёт псевдослучайные числа.
На основе этих
замечательных устройств можно легко написать простенькую функцию генерирования
случайных чисел:
// for low-level file working
#include
#include
#include
#include
// generate random numbers: [0..number)
int rnd(int number)
{
// read
random numbers from /dev/urandom
// for store
files descriptor
static int
dev_urandom=-1;
// errors
flags
bool
urandom_error=false;
bool
read_error=false;
int bytes;
uint data;
if(dev_urandom==-1)
{
dev_urandom=open("/dev/urandom",O_RDONLY);
if(dev_urandom==-1)
urandom_error=true;
}
if(!urandom_error)
{
bytes=read(dev_urandom,&data,sizeof(data));
if(bytes!=sizeof(data))
read_error=true;
else
{
data=data%(number+1);
}
}
return data;
}
Но главное не надо
забывать такого умного дядьку, как Джон фон Нейман, который говорил:
Если
уподобиться разного типа богоискателям можно сказать, что случайности(в нашем
случае - ГСЧ) -это один из языков Cтарика. Другие же применения ГСЧ чрезвычайно
интересны - от когнитивной эволючии и моделирования AI (читайте о Creativity Machine на membrana.ru) , до анализа безопасности (
вызывает умиление применение ГСЧ в статье
"Случайные числа упрощают алгоритм").
Но как всегда
человек с надеждой смотрит в будущее ,даже если оно определяется каким-то ГСЧ.
Дополнительная
информация 1. man
4 random 2. Теория
Вероятности (online-учебник)
3. random.org 4. RFC 1750 5. Ashby W. R. An introduction to
CYBERNETICS, CHAPMAN & HALL, London, 1956. (Русский перевод: Эшби У. Р. Введение в кибернетику,
Издательство иностранной литературы, М.: 1959) Очень советую достать и
прочитать эту книгу! В интернете можно скачать эл. вариант книги (на
английском), в формате .pdf
(около 2 Mb) на странице
http://pespmc1.vub.ac.be/ASHBBOOK.html Сам я нашёл эту книгу в своей
местной библиотеке, чего и вам желаю! 6. Д.Э. Кнут "Искусство
программирования" т.2
P.S. Эта статья
является некоторым итогом серии выпусков рассылки Моделирование Виртуальной
Вычислительной Системы. В этой статье автор выражает некоторые суждения,
которые могут быть весьма спорными, не претендуя на истину в последней
инстанции и глубину своих познаний в данной области автор с благодарностью
готов выслушать замечания и дополнения.
Список
литературы
Для подготовки
данной работы были использованы материалы с сайта http://www.bugtraq.ru/