Как работает генератор случайных чисел. Генераторы случайных чисел

Случалось ли вам когда-нибудь проверять утверждение, что из 10 запусков рулетки 5 раз выпадает чётное число? Или, быть может, вы участвовали несколько раз в розыгрышах лотерей и даже сумели выиграть? Если принять, что все результаты действительно случайны, то можно говорить о вероятности наступления того или иного события.

Перефразировав последнее утверждение, повторим слова людей, не один месяц участвующих в мероприятиях со случайным результатом: работает всемогущий рандом.

Так каким же образом проверить, является ли принцип распределения случайным? С этой задачей справится генератор случайных чисел. Главный его плюс в том, что он работает в режиме онлайн, а значит очень быстр и не зависит после загрузки от наличия интернет-соединения.

Как работает генератор случайных чисел

Для описания работы не потребуется много букв, всё очень просто: нужно выбрать минимальное и максимальное возможное число, ввести количество генерируемых значений, по необходимости отметить галочку «Исключить повторы», предотвращающую появление чисел, которые уже были, и нажать кнопку генерации. После этого, каждое очередное нажатие кнопки будет выдавать новые варианты распределения.

Для чего это может понадобиться? Например, для получения счастливых чисел в лотереи или рулетке. Помимо этого, генератор псевдослучайных чисел в состоянии эмулировать бочонки лото или подбрасывание монетки для конкурса - орёл и решка представляются нулём или единицей. Но основная примечательность в том, что после загрузки страницы вам не потребуется подключение к интернету - код написан на JavaScript и выполняется на стороне пользователя, в его браузере.

Тестирование работы данного онлайн генератора порой давало весьма интересные результаты: использование цифр 0 и 1, при 10 вариантах, не так уж редко выдавало распределение в соотношении 7 к 3, или даже 6 одинаковых цифр подряд.

Для чего ещё, кроме лото и примеров выше, может быть полезен рандом для распределения цифр? Хотя бы для игры в Угадайку. Наверняка в такую играли в детстве: ведущий загадывает число от 1 до 100, а другие пытаются его отгадать. Применительно к этому генератору, в роли ведущего выступаете вы, а компьютер пытается отгадать, что же загадано.

Можно даже играть в Морской бой, получив сразу группу чисел в диапазоне от 0 до 99. При этом, в качестве букв (которые указываются по горизонтали) используется старший разряд числа - 0…9 это а…и, цифры младшего разряда в таком случае заменяют диапазон 1…10, то есть просто добавляется единица. Возможно, сейчас данный подход кажется не очень наглядным, но это дело привычки.

Ещё один интересный способ использования - проверить свою интуицию. Вы пытаетесь предсказать, какие числа (по одному или группой) выдаст генератор, нажимаете кнопку и проверяете, насколько были близки к правильному результату. Кто знает, вдруг после нескольких попыток вы сможете безошибочно предугадывать итог?

Но следует учитывать, что генератор случ чисел так называется не зря. Существующие на сегодня методы не в состоянии обеспечивать действительно случайное значение - оно зависит от множества факторов, среди которых может быть предыдущее число, текущее время, содержимое той или иной ячейки памяти и прочие данные. Но для бытовых нужд их функционала, как правило, хватает на 100%.

Что же, надеюсь, что вы найдёте более обширное применение генератору, нежели описанные здесь варианты. А, быть может, даже сумеете предложить хорошую идею для расширения имеющегося функционала. В конце концов, именно самые невероятные мысли со временем превращались из расплывчатого замысла в реальное воплощение.

На макроскопических случайных процессах с использованием таких простых предметов, как игральная кость, колесо рулетки или монетка, могут быть основаны генераторы случайных чисел . Теорией хаоса и теорией неустойчивых динамических систем можно объяснить наличие непредсказуемости в данных и даже макроскопические системы, полностью определенные уравнениями Ньютона, на практике часто имеют непредсказуемый выход, так как зависит он от микроскопических деталей начальных условий.

Кстати, на нашем сайте вы можете cгенерировать случайное число, воспользовавшись Генератором случайных чисел онлайн .

Что такое генератор случайных чисел и как он использует случайные физические процессы?

Скорость получения случайных чисел , достаточную для прикладных задач, не могут обеспечить устройства, которые основаны на макроскопических случайных процессах. Источник шума, из которого происходит извлечение случайных битов, поэтому лежит в основе современных АГСЧ. Источники шума бывают двух видов: те, которые имеют квантовую природу и квантовые явления не использующие.

Некоторые природные явления, такие как радиоактивный распад атомов - абсолютно случайны и в принципе не могут быть предсказаны (опыт Дэвиссона — Джермера можно считать одним из первых опытов, которые доказывают вероятностную природу некоторых явлений), этот факт является следствием законов квантовой физики. А из статистической механики следует, что каждая система в своих параметрах имеет случайные флуктуации , если температура - не равняется абсолютному нулю.

Сложный генератор случайных чисел.

Для АГСЧ "золотым стандартом" являются некоторые из квантово-механических процессов, поскольку они абсолютно случайны. Использующие в генераторах случайных чисел явления включают:

• Дробовой шум - это тот шум, который в электрических цепях вызывается дискретностью носителей электрического заряда и этим термином также называется шум, вызванный в оптических приборах дискретностью переносчика света.
• Спонтанное параметрическое рассеяние, использовано также может быть в генераторах случайных чисел .
• Радиоактивный распад - имеет случайность каждого из отдельных актов распада, поэтому он используется в качестве источника шума. Разное количество частиц на различных промежутках времени, в результате попадает на приемник (это может быть счетчик Гейгера или же сцинтилляционный счетчик).

Детектировать гораздо проще неквантовые явления, но основанные на них генераторы случайных чисел , тогда будут иметь сильную зависимость от температуры (например, величина теплового шума будет пропорциональна температуре окружающей среды). Можно отметить такие процессы, среди использующихся в АГСЧ:

• Тепловой шум в резисторе, после усиления из которого получается генератор случайных напряжений . На этом явлении в частности, был основан генератор чисел в компьютере Ferranti Mark 1.
• Атмосферный шум, который измерен радиоприемником, также сюда можно отнести и прием прилетающих из космоса на Землю частиц, регистрирующихся приемником, а их количество будет случайно, в разные промежутки времени.
• Разница в скорости хода часов - это явление, которое заключается в том, что абсолютно не будет совпадать ход разных часов.

Чтобы из физического случайного процесса получить последовательность случайных битов , то для этого существует несколько подходов. Заключается один из них в том, что усиливается полученный сигнал-шум, затем фильтруется и подается на вход быстродействующего компаратора напряжений, для получения логического сигнала. Будет случайной длительность состояний компаратора и это позволяет создавать последовательность случайных чисел , проводя измерения этих состояний.

Второй подход состоит в том, что подается случайный сигнал на вход аналого-цифрового преобразователя (могут применяться как специальные устройства, так и аудиовход компьютера), представлять собой последовательность из случайных чисел, в результате которой будет оцифрованный сигнал и при этом она может быть программно обработана.

Что такое генератор случайных чисел и какие другие явления он использует?

Использующие физические случайные процессы генераторы случайных чисел , дают возможность для получения хороших случайных чисел, но производство их дорого и относительно сложно (особенно это касается тех АГСЧ, которые основаны на радиоактивном распаде), однако существуют и другие более доступные источники случайности:

Простая генерация случайных чисел.

Работы цифровых видеокамер, которые используют съемку макроскопических явлений, следует отнести к наиболее необычным генераторам. Так например, для генерации случайных чисел , командой из Silicon Graphics была использована видеозапись лавовой лампы потому, что воск хаотически меняет свои формы в лампе. Ленты от вентилятора в потоке воздуха или пузыри в аквариуме, могут быть также использованы в качестве объекта для съемки.

• Перевод

Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com - новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

К сожалению, ваша первая покупка в интернете была скомпрометирована с самого начала: вскоре обнаружится, что якобы безопасный протокол, по которому браузер установил соединение, на самом деле не очень защищён.

Проблема в том, что секретные ключи, которые использовал Netscape , были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса - все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.

Программисты Netscape с радостью бы использовали полностью случайные числа для генерации ключа, но не знали, как их получить. Причина в том, что цифровые компьютеры всегда находятся в точно определённом состоянии, которое меняется только при поступлении определённой команды от программы. Самое лучшее, что вы можете сделать - эмулировать случайность, генерируя так называемые псевдослучайные числа с помощью специальной математической функции. Набор таких чисел на первый взгляд выглядит полностью случайным, но кто-нибудь другой с помощью такой же процедуры может легко сгенерировать в точности такие же числа, так что обычно они плохо подходят для шифрования.

Исследователям удалось изобрести генераторы псевдослучайных чисел, которые признаны криптографически надёжными. Но их нужно запускать с качественного случайного начального значения (random seed), иначе они всегда сгенерируют один и тот же набор чисел. И для этого начального значения вам нужно нечто такое, что действительно невозможно подобрать или предсказать.

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

В течение последних лет в онлайне работает источник случайных чисел под названием Lavarand . Он был создан в 1996 году для автоматической генерации случайных значений путём обработки фотографий декоративного светильника - лавовой лампы, которая непредсказуемым образом меняет облик каждую секунду. С тех пор случайными значениями из этого источника воспользовались более миллиона раз.

Есть и более изощрённые аппаратные генераторы случайных чисел, которые регистрируют квантовые эффекты, например, удары фотонов в зеркало. Вы можете на самом обычном компьютере получить случайные числа путём регистрации непредсказуемых событий, таких как точное время нажатия на кнопки клавиатуры. Но чтобы получить большое количество таких случайных значений, придётся нажать немало кнопок.

Мы с коллегами в компании Intel решили, что нужно сделать более простой способ. Вот почему уже более десяти лет многие из чипсетов нашего производства содержат аналоговый аппаратный генератор случайных чисел. Проблема в том, что его аналоговый контур впустую расходует энергию. Вдобавок, трудно сохранить работоспособность этой аналоговой схемы по мере совершенствования техпроцесса по производству микросхем и их миниатюризации. Поэтому сейчас мы разработали новую и полностью цифровую систему, которая позволяет микропроцессору генерировать обильный поток случайных значений без этих проблем. Скоро этот новый цифровой генератор случайных чисел придёт к вам вместе с новым процессором.

Первая попытка Intel сделать лучший генератор случайных чисел на обычных ПК датируется 1999-м годом, когда компания Intel представила компонент Firmware Hub для чипсетов. Генератор случайных чисел в этом чипе (PDF) представляет собой аналоговый дизайн на базе кольцевого осциллятора, который регистрирует тепловой шум с резисторов, усиливает его и использует результирующий сигнал для изменения периода относительно медленного генератора тактовых импульсов. На каждый непредсказуемый «тик» этого медленного генератора микросхема накладывала частоту колебаний второго, быстрого генератора, который регулярно меняет своё значение между двумя бинарными состояниями: 0 и 1. В результате получается непредсказуемая последовательность нулей и единиц.

Проблема в том, что кольцевой осциллятор, который занимается усилением теплового сигнала, потребляет слишком много энергии - и он работает постоянно, независимо от того, нужны или нет компьютеру случайные числа в данный момент. Эти аналоговые компоненты также доставляют неудобства каждый раз, когда компания меняет техпроцесс производства микросхем. Каждые несколько лет компания модернизирует производственные линии, чтобы делать микросхемы в более миниатюрном масштабе. И каждый раз этот аналоговый фрагмент нужно по-новому калибровать и тестировать - эта сложная и кропотливая работа стала настоящей головной болью.

Вот почему в 2008 году Intel принялась за разработку генератора случайных чисел, который работает исключительно на цифровой основе. Исследователи компании в Хиллсборо (Орегон, США), совместно с инженерами Design Lab в Бангалоре (Индия) начали изучать ключевую проблему - как получить случайный поток битов без использования аналоговых схем.

Забавно, но предложенное ими решение нарушает основное правило цифрового дизайна, что схема должна всегда быть в определённом положении и возвращать либо логический 0, либо 1. Конечно, цифровой элемент может проводить краткосрочные промежутки времени в неопределённом положении, переключаясь между этими двумя значениями. Однако, он должен работать предельно чётко и никогда не должен колебаться между ними, иначе это вызовет задержки или даже сбой в системе. В нашем же генераторе случайных битов колебания являются фичей, а не багом .

Наш предыдущий аналоговый генератор был способен выдавать только пару сотен килобит случайных чисел в секунду, в то время как новый генерирует их потоком около 3 Гб/с. Он начинает работу, собирая практически случайные значения двух инвертеров блоками по 512 бит. В дальнейшем эти блоки разбиваются на пары 256-битных чисел. Конечно, если оригинальные 512 бит не полностью случайны, эти 256-битные числа тоже не будут полностью случайными. Но их можно математически скомбинировать таким образом, чтобы получить 256-битное число, близкое к идеальному.

ТРИ УРОВНЯ ЧИСЕЛ: Генератор случайных чисел Intel Bull Mountain предотвращает любые варианты предсказуемости с помощью трёхступенчатого процесса. Сначала цифровой контур генерирует поток случайных битов. Потом «нормализатор» (conditioner) генерирует на основе этого потока хорошие случайные начальные значения (random seeds). На третьем этапе генератор псевдослучайных чисел выдаёт поток цифр для использования в программном обеспечении.

Всё это лучше показано на простой иллюстрации. Предположите на секунду, что генератор случайных битов выдаёт 8-битные комбинации, то есть как бы числа в диапазоне от 0 до 255. Предположите также, что эти 8-битные числа не полностью случайны. Теперь представьте, что, к примеру, какой-то неуловимый изъян в цепи смещает выдаваемые значения в нижнюю часть диапазона. На первый взгляд, поток случайных чисел кажется хорошим, но если вы обработаете миллионы значений, то заметите, что числа из верхней части диапазона встречаются немножко реже, чем числа из нижней части.

Одно из возможных решений этой проблемы простое: всегда берите пару 8-битных чисел, перемножайте их, а потом отбрасывайте верхние восемь бит из получившегося 16-битного числа. Такая процедура устранит перекос практически целиком.

Bull Mountain не работает с 8-битными числами: он работает, как уже было сказано, с 256-битными числами. И он их не перемножает, а производит более сложные криптографические операции. Но основная идея та же самая. Вы можете представить этот этап как «нормализацию» по устранению тех отклонений от случайного распределения чисел, которое может возникнуть в схеме с двумя инвертерами.

Нам действительно хочется хорошо спать по ночам, так что спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам. Таким образом, операции производятся только с качественными парами чисел.

Гарантированной случайности недостаточно, если случайные значения не выдаются достаточно быстро, чтобы соответствовать стандартам. Хотя аппаратный контур генерирует поток значительно быстрее, чем его предшественники, этого всё ещё недостаточно для некоторых современных задач. Чтобы Bull Mountain мог выдавать случайные числа так же быстро, как выдают поток программные генераторы псевдослучайных чисел, но при этом сохранять высокое качество случайных чисел, мы добавили ещё один уровень в схему. Здесь 256-битные случайные числа используются как криптографически надёжные начальные значения (random seeds) для генерации большого количества псевдослучайных 128-битных чисел. Поскольку 256-битные числа поступают с частотой 3 ГГц, то гарантируется достаточное количество материала для быстрой генерации криптографических ключей.

Новая инструкция под названием RdRand даёт возможность программе, которой нужны случайные числа, обратиться с запросом к аппаратному обеспечению, которое их производит. Созданная для 64-битных процессоров Intel, инструкция RdRand - это ключ к генератору Bull Mountain. Она извлекает 16-, 32- или 64-битные случайные значения и помещает их в регистр, доступный для программы. Инструкция RdRand была открыта для публики около года назад, и первым процессором Intel, который будет поддерживать её, станет Ivy Bridge. Новый чипсет работает на 37% быстрее, чем его предшественник, а размер его минимальных элементов уменьшен с 32 до 22 нанометров. Общее увеличение производительности хорошо сочетается с потребностями нашего генератора случайных чисел.

Хотя лавовые лампы выглядят круто , они впишутся не в каждый интерьер. Мы думаем, что наш подход к генерации случайных чисел, напротив, найдёт самое универсальное применение.

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

Все явления, которые с нами происходят, бывают двух типов – случайные и закономерные. Например, у вас недоставало для покупки магнитофона немножко купюр, и вы решили купить плеер – т.е. поступок является логичным и ожидаемым. Но, идя к магазину, вы обнаруживаете нужную сумму, которая случайным образом изменила планы. Работа генератора случайных чисел полностью зависит от заданного в оператор механизма, так что все числа, которые выдаются, в текущем событии являются псевдослучайными. Операторы, возвращающие случайные числа , обращаются ко времени, а именно системному. Т.е. как в мире, так и в программировании не бывает ничего всецело абсолютного.

Функция rand

В программировании на си, для получения случайных значений изобрели встроенные операторы, которые выдают нам требуемые результаты. И так, для создания случайного числа применяется функция rand , которая Оператор rand применяется для получения случайных чисел, которые возвращают диапазон от 0, и до определенной константы. Причем данная константа объявляется в системной директиве “stdlib.h”, там и базируется эта функция rand. Синтаксис этой функции прост: int m= rand(); т.е. выдается целое число. Опробовав оператор на практике, вы увидите, что появляющиеся числа при старте приложения идентичные. Оплошность заключается в том, что оператор rand работает с одним и тем же системным временем, которое сохранилось при компиляции. Данный генератор случайных чисел завязан на алгоритме изменения программного времени, то все работает неверно.

Теперь о srand и random

Для данной проблемы, незаменима была функция, которая б обнуляла встроенное время при каждом обращении к оператору rand, и разработчики ПО сделали функцию srand . Действие позволяет функции rand каждый раз обращаться не к установленному, а к текущему встроенному таймеру, что открывает возможность работать генератору верно – выдавать случайные значения. Недавно в программирования си ++ усовершенствовался механизм выдачи случайных чисел, из-за появления микросекунд. К тому же расширился диапазон значений, и все текущие новшества трансформировались в функцию random.

Что такое случайность в компьютере? Как происходит генерация случайных чисел? В этой статье мы постарались дать простые ответы на эти вопросы.

В программном обеспечении, да и в технике в целом существует необходимость в воспроизводимой случайности: числа и картинки, которые кажутся случайными, на самом деле сгенерированы определённым алгоритмом. Это называется псевдослучайностью, и мы рассмотрим простые способы создания псевдослучайных чисел. В конце статьи мы сформулируем простую теорему для создания этих, казалось бы, случайных чисел.

Определение того, что именно является случайностью, может быть довольно сложной задачей. Существуют тесты (например, колмогоровская сложность), которые могут дать вам точное значение того, насколько случайна та или иная последовательность. Но мы не будем заморачиваться, а просто попробуем создать последовательность чисел, которые будут казаться несвязанными между собой.

Часто требуется не просто одно число, а несколько случайных чисел, генерируюемых непрерывно. Следовательно, учитывая начальное значение, нам нужно создать другие случайные числа. Это начальное значение называется семенем , и позже мы увидим, как его получить. А пока давайте сконцентрируемся на создании других случайных значений.

Создание случайных чисел из семени

Один из подходов может заключаться в том, чтобы применить какую-то безумную математическую формулу к семени, а затем исказить её настолько, что число на выходе будет казаться непредсказуемым, а после взять его как семя для следующей итерации. Вопрос только в том, как должна выглядеть эта функция искажения.

Давайте поэкспериментируем с этой идеей и посмотрим, куда она нас приведёт.

Функция искажения будет принимать одно значение, а возвращать другое. Назовём её R.

R(Input) -> Output

Если значение нашего семени 1, то R создаст ряд 1, 2, 3, 4, … Выглядит совсем не случайно, но мы дойдём до этого. Пусть теперь R добавляет константу вместо 1.

Если с равняется, например, 7, то мы получим ряд 1, 8, 15, 22, … Всё ещё не то. Очевидно, что мы упускаем то, что числа не должны только увеличиваться, они должны быть разбросаны по какому-то диапазону. Нам нужно, чтобы наша последовательность возвращалась в начало — круг из чисел!

Числовой круг

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

Здесь мы получаем очень важно свойство: если наш цикл состоит из n элементов, то максимальное число элементов, которые мы можем получить перед тем, как они начнут повторяться это n.

Теперь давайте переделаем функцию R так, чтобы она соответствовала нашей логике. Ограничить длину цикла можно с помощью оператора модуля или оператора остатка от деления.

R(x) = (x + c) % m

На этом этапе вы можете заметить, что некоторые числа не подходят для c. Если c = 4, и мы начали с 1, наша последовательность была бы 1, 5, 9, 1, 5, 9, 1, 5, 9, … что нам конечно же не подходит, потому что эта последовательность абсолютно не случайная. Становится понятно, что числа, которые мы выбираем для длины цикла и длины прыжка должны быть связаны особым образом.

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали «прыжки» за счёт добавления, но что если использовать умножение? Умножим х на константу a .

R(x) = (ax + c) % m

Свойства, которым должно подчиняться а, чтобы образовался полный цикл, немного более специфичны. Чтобы создать верный цикл:

1. (а — 1) должно делиться на все простые множители m
2. (а — 1) должно делиться на 4, если m делится на 4

Эти свойства вместе с правилом, что m и с должны быть взаимно простыми составляют теорему Халла-Добелла. Мы не будем рассматривать её доказательство, но если бы вы взяли кучу разных значений для разных констант, то могли бы прийти к тому же выводу.

Выбор семени

Настало время поговорить о самом интересном: выборе первоначального семени. Мы могли бы сделать его константой. Это может пригодиться в тех случаях, когда вам нужны случайные числа, но при этом нужно, чтобы при каждом запуске программы они были одинаковые. Например, создание одинаковой карты для каждой игры.

Еще один способ — это получать семя из нового источника каждый раз при запуске программы, как в системных часах. Это пригодится в случае, когда нужно общее рандомное число, как в программе с бросанием кубика.

Конечный результат

Когда мы применяем функцию к её результату несколько раз, мы получаем рекуррентное соотношение. Давайте запишем нашу формулу с использованием рекурсии.