28539

Получение случайных чисел

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-08-20

45 KB

25 чел.

Получение случайных чисел

Последовательность случайных чисел можно получить одним из следующих способов:

- путем выборки из специальных таблиц

- используя датчики случайных чисел

- программными методами.

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

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

                             Метод произведений  

Произвольно выбираются два числа b0 и b1 , имеющие одинаковое число  значащих цифр m. Находится их произведение q2 =b0 b1 . Если m > 1, то  число значащих цифр в q2 будет больше, чем m. Тогда из всех значащих цифр  произведения q2 выбирается m цифр, расположенных в середине числа q2, и эти цифры используют как случайное число b2. Следующее случайное  число b3 получается аналогично из произведения b1 b2 и т.д.

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

Применение метода вычетов основано на том, что каждое последующее

случайное число bk+1 образуется из предыдущего bk согласно рекуррентному  соотношению:

 bk+1 =l*bk(modN)   (1)  

которое означает, что число b равно остатку от деления на N произведения

числа b на постоянный множитель l. Очевидно, что остаток от деления на

 N в общем случае имеет туже разрядность, что и число N, т.е. выбором числа  N по существу определяется разрядность получаемых случайных чисел.

С использованием этого алгоритма была, например, найдена следующая  зависимость для получения последовательности псевдослучайных чисел b ,  равномерно расположенных на интервале [0;1]:  

dk+1 =517*d (mod 242 ); d0 = 1;   (2)  

 

bk =2-42 *dk   (3)  

Уравнение (2) является записью алгоритма (1), а (3) применяется для того,

чтобы привести случайные числа к интервалу [0; 1]. Период последовательности, получаемый по (2) примерно равен 1210 .Другая последовательность

псевдослучайных чисел может быть получена при использовании рекуррентного

соотношения (1), если принять  l=513;    n=236   (4)  

Получаемая при этих значениях последовательность имеет период,  оцениваемый  числом 22.1010 .

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

Получение псевдослучайных последовательностей из иррациональных   чисел.  Этот способ основан на свойстве иррациональных чисел образовывать  неупорядоченную последовательность цифр дробной части при вычислении  иррационального числа с достаточно высокой степенью точности.  В наиболее простой форме данный способ реализуется при расчете дробной  части произведения иррационального числа Z на последовательность  натуральных чисел. При этом алгоритм может быть записан в следующем  виде: bk= {K*Z}   K=1; 2; 3...   (5)  

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

                       Генерирование псевдослучайных чисел

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

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

Одной из задач при использовании конгруэнтных генераторов является  подбор чисел-параметров генератора.  "Из простейших процедур, имитирующих случайные числа, наиболее  употребляемым так называемый конгруэнтный способ, приписываемый  Д.Х.Ламеру (Вообще-то он D.H.Lehmer):

    G(n+1)=K*G(n) + C MOD M

В нем каждое псевдослучайное число G(n+1) получается из предыдущего

 G(n1) умножением его на K, сложением с C и взятием остатка от деления

на M. Весь фокус здесь в том, чтобы подобрать хорошие значения K,C и

 M, на что были потрачены десятилетия работы математиков. Подбор почти

иррациональных K ничего не дает. Разумнее вычисления вести в целых

числах. Для них было установлено, что при C=0 и M=2^n наибольший

период M/4 достигается при K=3+8*i или K=5+8*i и нечетном начальном

числе. При достаточно больших K ряд производит впечатление случайного.

Результат можно улучшить если C нечетно и K=1+4*i, то период ряда равен  M. После долгих поисков K исследователи остановились на  значениях  69069 и 71365. Кроме значений M=2^N широко используются выборы  простых M, например, простого числа M=2^31 -1, известного со времен  Эйлера." Hаиболее  эффективным из псевдослучайных генераторов  является циклический генератор с обратной связью. Описан в книге  "Хоровиц, Хилл - Искусство схемотехники". Если период повторения  псевдослучайного генератора слишком мал, используют XOR нескольких  генераторов с взаимно простыми периодами. Период такого агрегированного  генератора есть произведение периодов элементарных генераторов.

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

Аппаратные генераторы

Hастоящие же генераторы истинно случайных последовательностей делают  в виде аппаратного устройства (или компьютерной карты).  Самым лучшим таким генератором является счетчик Гейгера + какой-нибудь  слаборадиоактивный изотоп. В таком генераторе меряется время между "щелчками"  моментами, когда генератор поймал частицу. Такой генератор дает очень хорошее  нормальное распределение, и обладает высокой производительностью. Применяется  в крипто-штучках, где гарантировано необходима истинно случайная уникальная  последовательность.

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


 

А также другие работы, которые могут Вас заинтересовать

20694. Единая Европа: источники, образование, перспективы 136.5 KB
  ЕС является ключевым политическим и экономическим партнером России на Западе даже в условиях санкций. Особенно активно развиваются торгово-экономические связи. ЕС и Россия должны быть направлены на дальнейшее развитие конструктивного сотрудничества. В связи с этим понимание истоков, идей создания ЕС и его развитие является актуальным.
20695. ФОРМЫ УЧАСТИЯ ПРОКУРОРА В ГРАЖДАНСКОМ СУДОПРОИЗВОДСТВЕ В РК И ЗАРУБЕЖНЫХ СТРАНАХ 186 KB
  Дискуссия по поводу ограничения или, наоборот, усиления роли прокурора как в суде, так и в общем надзоре, не являются на сегодняшний день чем-то новым в истории прокуратуры, для которой характерен непрекращающийся поиск оптимальных форм осуществления полномочий.
20696. Розв’язання систем нелінійних рівнянь. Метод Ньютона 18.5 KB
  0001; J = [diffy1'x1' diffy1'x2' diffy1'x3' ; diffy2'x1' diffy2'x2' diffy2'x3' ; diffy3'x1' diffy3'x2' diffy3'x3' ]; p=[2;2;2]; x1=p1; x2=p2; x3=p3; dp=[inf;inf;inf]; while maxabsdp1:3 eps dp=[0;0;0]; Fk=[0;0;0]; Jk=evalJ; for i=1:3 Fki=evalFi:; end dp=invJkFk; p=pdp; x1=p1; x2=p2; x3=p3; end p 2.
20697. Криптографічна система RSA 54.28 KB
  5 зашифруємо повідомлення Створемо ключ Зашифруємо файл Відповідно до завдання лабораторної роботи проведемо розрахунки Повідомлення CRDHQS RSA p=5 q=7 N=57=35 p1q1=24 D=5 edmodp1q1=1 e5mod24=1 E=5 Ключ24 e =5 3^5 mod 35=33 18^5 mod 35=23 4^5 mod 35=9 8^5 mod 35=8 17^5 mod 35=12 19^5 mod 35=24 Зашифроване повідомлення 33 23 9 8 12 24 Розшифруєм повідомлення використовуючи ключ d=5 33 33^5 mod 35=3 23^5 mod 35=18 9^5 mod 35=4 8^5 mod 35=8 12^5 mod 35=17 24^5 mod 35=19 Висновки:...
20698. Розподіл ключів, протокол Діфф-Хеллмана 57.93 KB
  При роботі алгоритму кожна сторона: генерує випадкове натуральне число a закритий ключ спільно з віддаленою стороною встановлює відкриті параметри p і g зазвичай значення p і g генеруються на одній стороні і передаються іншій де p є випадковим простим числом g є первісних коренем по модулю p обчислює відкритий ключ A використовуючи перетворення над закритим ключем A = ga mod p обмінюється відкритими ключами з видаленою стороною обчислює загальний секретний ключ K використовуючи відкритий ключ видаленої сторони B і свій закритий ключ a...
20699. Еліптичні криві в криптографії 168.01 KB
  1КІ08 Морозов Артем Еліптична крива над полем K це множина точок проективної площини над K що задовольняють рівнянню разом з точкою на нескінченності. Отже кількість точок на кривій – парна 1 точку дає по дві точки можуть давати інші елементи поля і треба не забути про точку на нескінченності. Додавання точок виконується наступним чином: 1 Нейтральний елемент групи: для будьякої точки . 3 Якщо то сумою точок та є 4 Якщо то 5 Якщо то .
20700. Генерування випадкових чисел 89.26 KB
  1КІ08 Морозов Артем Мета роботи: Усвідомити важливість проблеми генерування випадкових чисел під час вирішення задач захисту інформації ознайомитися з деякими способами генерування псевдовипадкових чисел усвідомити сильні і слабкі сторони алгоритмічних методів генерування випадкових чисел. Генератор випадкових чисел англ. Широко використовуються комп'ютерні системи для генерації випадкових чисел але часто вони малоефективні.
20701. Cтенографічний захист інформації 165.67 KB
  Для запуску програми необхідно задати: 1 звуковий файл формату МРЗ; 2 впроваджуваний файл будьякого формату; 3 пароль; 4 коефіцієнт стиснення; 5 рівень скритності. На першому етапі роботи програми впроваджуваний файл стискається з заданим користувачем коефіцієнтом стиснення. Блоксхема алгоритму роботи програми Puff представлена ​​на рисунку. Відповідно до класифікації методів впровадження інформації всі розглянуті в статті програми реалізують форматні методи.
20702. Гамування 75.04 KB
  Відкрите повідомлення MYNAMEІSARTEM Зашифруемо повідомлення Ключ k=i36mod 26 MYNAMEISARTEM 1 2 3 4 5 лат. Зашифроване повідомлення Шифрування Ci=tigimod N 16 8 4 2 1 k=i36 1 2 3 4 5 21 0 1 1 1 0 7 1 0 1 1 0 16 0 0 0 1 0 20 1 0 1 1 0 15 0 1 0 1 0 16 0 0 0 1 0 14 1 0 0 1 0 11 0 0 0 0 0 15 0 1 0 1 0 15 0 1 0 1 0 8 1 0 1 1 1 9 1 1 1 0 1 17 0 0 1 0 1 11 0 1 1 1 1 Висновки: В даній лабораторній роботі було розглянуто принципи гамування створено гаму і зашифровано за допомогою неї повідомлення.