Меню

Как составить алгоритм генератора



Как составить алгоритм генератора

Алгоритм работы генератор случайных чисел «Generator-Chisel.ru» основан на базе Вихря Мерсенна. Сам же, Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных по критерию случайности псевдослучайных чисел.

Вихрь Мерсенна лишён многих недостатков, присущих другим ГПСЧ (генератор псевдослучайных чисел), таких как малый период, предсказуемость, легко выявляемые статистические закономерности. Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (TGFSR) (англ. twisted generalised feedback shift register). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5 измерениями). Поэтому функция корреляции между двумя последовательностями выборок в выходной последовательности вихря Мерсенна пренебрежимо мала. Псевдослучайная последовательность, порождаемая вихрем Мерсенна, имеет очень большой период, равный числу Мерсенна, что более чем достаточно для многих практических приложений. Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2—3 раза быстрее линейных конгруэнтных генераторов). Алгоритм вихря Мерсенна реализован в программной библиотеке Boost, Glib и стандартных библиотеках для C++, Python, Ruby, R, PHP, MATLAB, Autoit. Выдаваемые вихрем Мерсенна последовательности псевдослучайных чисел успешно проходят статистические тесты DIEHARD, что подтверждает их хорошие статистические свойства.

Алгоритм работы Вихря Мерсенна алгоритмически реализуется двумя основными частями: рекурсивной и закалки. Рекурсивная часть представляет собой регистр сдвига с линейной обратной связью, в котором все биты в его слове определяются рекурсивно; поток выходных битов определяются также рекурсивно функцией битов состояния. Регистр сдвига состоит из 624 элементов, и, в общей сложности, из 19937 клеток. Каждый элемент имеет длину 32 бита за исключением первого элемента, который имеет только 1 бит за счет отбрасывания бита. Процесс генерации начинается с логического умножения на битовую маску, отбрасывающей 31 бита (кроме наиболее значащих). Следующим шагом выполняется инициализация (x0, x1,…, x623) любыми беззнаковыми 32-разрядными целыми числами. Следующие шаги включают в себя объединение и переходные состояния. Пространство состояний имеет 19937 бит (624·32 — 31). Следующее состояние генерируется сдвигом одного слова вертикально вверх и вставкой нового слова в конец. Новое слово вычисляется гаммированием средней части с исключённой[13]. Выходная последовательность начинается с x624, x625,…

Алгоритм производится в шесть этапов(шагов):

Шаг 0. Предварительно инициализируется значение констант u, h, a
u ← 10…0 битовая маска старших w-r бит,
h ← 01…1 битовая маска младших r бит,
aaw-1aw-2…a последняя строка матрицы A.

Шаг 3. Вычисляется значение следующего элемента последовательности по рекуррентному выражению (1)
x[i] ← x[(i + m) mod n] XOR (y>>1) XOR a если младший бит y = 1

Источник

Алгоритм генерации кода

Алгоритм генерации кода получает на входе последовательность трехадресных инструкций, составляющих базовый блок. Для каждой трехадресной инструкции вида х : = у op z мы выполняем следующие действия:

1. Вызываем функцию getreg для определения места L, где должен быть сохранен результат вычисления у op z. Обычно L представляет собой регистр, но может быть и ячейкой памяти. Далее мы вкратце опишем работу функции getreg.

2. Обращаемся к дескриптору адресов у для определения у’, текущего положения у (или одного из них). Если значение у есть и в памяти, и в регистре, в качестве у’ предпочтительнее регистр. Если значение у еще не находится в L, генерируем инструкцию MOV у’, L для размещения копии у в L.

3. Генерируем инструкцию OP z‘, L, где z‘ – текущее положение z. Здесь также, если значение z есть и в регистре, и в памяти, предпочитается регистр. Обновляем дескриптор адреса х с тем, чтобы в нем хранилась информация о том, что местоположением х является L. Если L представляет собой регистр, обновляем его дескриптор для указания того, что он содержит значение х, и удаляем х из других дескрипторов регистров.

4. Если текущие значения у и/или z в дальнейшем не используются, не являются живыми при выходе из блока и находятся в регистрах, то изменим соответствующие дескрипторы регистров, чтобы указать, что после выполнения х : =у op zэти регистры более не содержат у и/или z.

Если текущая трехадресная инструкция содержит унарный оператор, предпринимаемые шаги аналогичны приведенным выше, так что мы опускаем их подробное описание.

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

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

Читайте также:  Дизель генератор зачем нужен

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

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

Источник

Алгоритмы генерации случайных чисел. алгоритм аддитивного конгруэнтного генератора псевдослучайной последовательности.

Простейшие алгоритмы генерации псевдослучайных последовательностей

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

Использование стандартных функций языков высокого уровня

Функция Rand() выдает псевдослучайное число в указанном диапазоне (способ задания диапазона отличается в различных языках). Начальная инициализация генератора случайных чисел происходит при помощи системного вызова специальной функции. Для C – это функция srand, а для Object Pascal задание начального значения реализовано через свойство RandSeed, в Basic – randomaze.

Все эти функции генерируют псевдослучайные числа в указанном диапазоне.

Генерация псевдослучайных последовательностей (ПСП) давно занимала математиков и одним из первых способов было предложено получать их как значения дробной части многочлена первой степени:

Yn = Ent (a•n+b), где Ent – дробная часть полученного выражения.

Если n пробегает значения натурального ряда чисел, то поведение Yn выглядит весьма хаотичным. Еще Карл Якоби доказал, что при рациональном коэффициенте а множество конечно, а при иррациональном – бесконечно и всюду плотно в интервале от 0 до 1.

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

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

, ,

где Т0 – исходная величина, т.е. число, порождающее последовательность; М – обычно 2b – длина слова в битах 28, 216 и т.д.; А, C – подбираются таким образом, чтобы период порождающей последовательности был максимальным. Доказано, что он максимален, когда C – нечетное, (А mod4)=1.

Например, если выбрать С=3, А=5, M=256, t0=1, то получим следующую последовательность чисел:

t1 =8; t2 =43;…t254 =71; t255 =102; t256 =1; t257=8; t258 =43… .

Видно, что период полученной последовательности равен 28. В реальной ситуации величина M обычно составляет 216, 232, 264.

,

где , M=231-1.

Иногда используют квадратичные и кубические конгруэнтные генераторы, которые обладают большей стойкостью к взлому.

Квадратичный конгруэнтный генератор имеет вид

.

Кубический конгруэнтный генератор задается как

.

Для увеличения размера периода повторения конгруэнтных генераторов часто используют их объединение. При этом криптографическая безопасность не уменьшается, но такие генераторы обладают лучшими характеристиками в некоторых статистических тестах.

Реальные генераторы случайных последовательностей

Для любого генератора важным вопросом является его проверка. Тесты на случайность можно найти в Internet. Доказано, что все из описанных выше генераторов можно воспроизвести. Это только вопрос времени.

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

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

1. Использование специальных таблиц RAND.

2. Использование случайного шума.

3. Использование таймера компьютера.

4. Измерение скрытого состояния клавиатуры.

Читайте также:  Бак для охлаждения генератора

5. Аппаратно-временные характеристики компьютера:

— положение мыши на экране монитора;

— текущий номер сектора и дорожки дисковода или винчестера;

— номер текущей строки развертки монитора;

— времена поступления сетевых пакетов.

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

1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.

2. Гамма должна быть трудно предсказуемой. Это значит, что если известны тип генератора и кусок гаммы, то невозможно предсказать следующий за этим куском бит (или число) гаммы с вероятностью выше заданной P. Если криптоаналитику станет известна какая-то часть гаммы, он все же не сможет определить биты, предшествующие ей или следующие за ней.

3. Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.

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

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

Статьи к прочтению:

✅На что способна микроволновка! Генерация ПЛАЗМЫ

Похожие статьи:

Как уже отмечалось ранее, имитационное моделирование ЭИС, как правило, предполагает необходимость учета различных случайных факторов — событий, величин,…

Генератор, формирующий очередное случайное число в соответствии с отношением (3), называется аддитивным: Xn+1=(Xn+Xn-k) mod m. (3) В трехтомнике Кнута…

Источник

Что такое ГСЧ – как работает генератор случайных чисел

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

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

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

Истинный ГСЧ против псевдо ГСЧ

Есть два типа генераторов случайных чисел: истинные и псевдо.

  • Алгоритм истинного генератора случайных чисел создаётся с помощью аппаратного устройства, которое использует очень крошечные физические процессы для генерации случайных чисел. Так как алгоритм не написан; следовательно, истинный ГСЧ не может быть взломан для предсказания. Он обычно используется в системах, ориентированных на безопасность, по всему миру и в некоторых формах шифрования.
  • Алгоритм генератора псевдослучайных чисел используется в областях, где нет проблем с безопасностью, а случайность используется, чтобы избежать повторений и сделать что-то более интересное для конечного пользователя. Реализовать технологию дешевле и быстрее, поскольку она не требует оборудования и может быть легко встроена в программный код. Хотя этот процесс не является полностью случайным и определяется на основе алгоритма, он больше подходит для игр и программ.

Какие приложения используют ГСЧ

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

  • Азартные игры: бинго, карточные игры, лотереи и подобные игры.
  • Игры со сбором добычи: все игры, требующие от игроков сбора добычи для использования в игровом процессе, например, PubG, Diablo и Borderlands используют ГСЧ. Возможность получать лучшую добычу каждый раз – вот причина, по которой люди становятся зависимыми от них.
  • Приключенческие игры: такие игры, как Марио и Покемон Го используйте алгоритм генератора случайных чисел, чтобы определить, какие предметы будут добавлены, и каждый раз вы встречайтесь с новым претендентом на покемона.
  • Процедурно-сгенерированные игры: все игры, в которых нет предварительно разработанных карт и уровней, но которые были разработаны в игре с использованием процедурного программирования, таких как Minecraft и Civilization. Это помогает создать всю игру с использованием алгоритма.
  • Соревновательные игры: некоторые соревновательные игры, например, Counter-Strike используйте алгоритм генератора случайных чисел, чтобы регулировать, как пули поражают цели.
Читайте также:  Щетки генератора дэу нексия 16 клапанов замена

Помимо игровых приложений, есть код случайных чисел в JavaScript, используемый разработчиками и кодировщиками во всём мире для включения генератора случайных чисел в их программы. У Google есть свой очень интересный инструмент, который также основан на теории случайных чисел JavaScript и может генерировать случайные числа. Этот инструмент может пригодиться, когда вы играете в игры с друзьями и семьей. Чтобы посмотреть ГСЧ Google, нажмите здесь.

Манипуляции с ГСЧ

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

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

Например, если игра требует от игрока выбрать определенного персонажа с определенными усилениями, и результатом будет легкая битва с боссом, то этот шаблон будет постоянным, и все, кто выберет одни и те же варианты, будут иметь одинаковые результаты. Но, для обычного игрока это было бы невозможно, и псевдо-ГСЧ всегда казался бы истинным ГСЧ.

Почему геймеры ненавидят ГСЧ

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

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

Кто такой RNGesus?

Обычные игроки, которые играют только для того, чтобы развлечься или скоротать время, не заботятся о результате игры. Но, опытные профессиональные игроки ненавидят проигрывать только потому, что удача была не в их пользу.

Игроки, которые проигрывают, часто винят в своих поражениях злой ГСЧ, который выгоден их противникам. Там где зло, должен быть Бог – RNGesus.

Среди геймеров во всем мире появился новый термин, RNGesus, который больше соответствует игре слов с «Иисусом». Поскольку Иисус Христос считается нашим спасителем в реальном мире, RNGesus – это вообразимая сущность, созданная для спасения игроков от пагубных последствий ГСЧ. Это нигде не доказывается, но началось как миф, а теперь распространилось по игровому сообществу, как лесной пожар.

Окончательный вердикт по ГСЧ – хорошо или плохо?

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

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

Игры предназначены для развлечения и удовольствия. Если у вас хороший ГСЧ, вы сможете получить лучшие варианты, несмотря на низкие шансы. В случае плохого ГСЧ, вы получите худший результат, даже если вы играли в игру именно так, как должно. Правда в том, что это не то, что можно воспринимать так серьёзно, особенно если оно основано на алгоритме генератора случайных чисел.

Источник