*https://www.youtube.com/watch?v=mVF8NDM-reg
**https://300.ya.ru/v_cKXj0aIm
Таймкоды
00:00:04 Случайные числа и шум
- Случайные числа можно получать из хаотичных процессов, например, из телевизионного шума.
- Случайная последовательность представлена как путь с непредсказуемыми направлениями.
- Случайные процессы недетерминированы, в отличие от детерминированных автоматов.
00:01:11 Алгоритм Джона фон Неймана
- Фон Нейман использовал компьютер ENIAC для расчётов при разработке водородной бомбы.
- Для генерации случайных чисел он придумал алгоритм, основанный на начальном значении.
- Начальное значение может быть взято из шума или текущего времени.
00:01:51 Метод серединных квадратов
- Метод серединных квадратов: возведение числа в квадрат и взятие средних цифр.
- Последовательность зависит только от начального значения.
- Метод стал первым из множества генераторов псевдослучайных чисел.
00:02:17 Разница между случайными и псевдослучайными последовательностями
- Псевдослучайная последовательность обязательно повторится, если начальное значение будет использовано повторно.
- Период повторения ограничен размером начального значения.
- При большом начальном значении алгоритм может выдать триллионы чисел до повторения.
00:03:07 Ограничения псевдослучайных последовательностей
- Из двузначного начального значения можно получить максимум 100 чисел.
- Из трёхзначного начального значения — не более 1000 чисел.
- Из четырёхзначного начального значения — не более 10 000 чисел.
00:04:06 Преимущества псевдослучайных генераторов
- Псевдослучайные генераторы уменьшают пространство ключей до меньшего размера начального значения.
- Защита возрастает с длиной начального значения.
- Даже мощный компьютер не сможет перебрать все возможные значения за разумное время.
00:05:23 Применение псевдослучайных алгоритмов
- Псевдослучайные алгоритмы позволяют обмениваться короткими начальными значениями без необходимости передачи длинных случайных цепочек.
- Это упрощает взаимодействие между устройствами.
- В следующих видео будет рассмотрено, что произойдёт, если обмен начальными значениями невозможен.
Расшифровка видео
0:04
в реальном мире мы часто сталкиваемся
0:07
со случайно
0:08
порядком
0:09
действительно случайно
0:11
числа можно получать из хаотичных
0:13
процессов из так называемого шума
0:16
слушая такой шум и дело и выборки из
0:19
него можно получать числа
0:21
например слушая телевизионный шум можно
0:24
получить истина случайную
0:25
последовательность
0:27
эту случайную последовательность можно
0:30
представить в виде пути
0:32
где через каждый шаг в зависимости от
0:34
числа меняется направление
0:36
так называемое случайное блуждание
0:39
обратите внимание на полное отсутствие
0:42
закономерностей в каждой точке пути
0:44
следующий шаг абсолютно непредсказуем
0:47
случайные процессы являются
0:49
недетерминированными их невозможно
0:51
детерминировать то есть предсказать а
0:54
вот автоматы
0:55
наоборот ветер минирован и и их действия
0:59
можно предсказать
1:00
и воспроизвести в 1946 году джон фон
1:04
нейман помогал проводить расчеты для
1:06
военных в частности участвовал в
1:08
разработке водородной бомбы при помощи
1:11
компьютера eniac он аппроксимировать
1:14
процессы происходящие при расщеплении
1:16
ядра для этого ему требовались длинные
1:20
последовательности случайных чисел
1:21
которые можно было бы запомнить и
1:24
повторить в компьютере
1:26
eniac было слишком мало памяти и хранить
1:28
готовые последовательности
1:30
не получалось и фон нейман придумал
1:33
алгоритм позволившая генерировать
1:35
случайность при помощи автомата
1:37
во-первых выберем некое действительно
1:39
случайное число и назовем его сид от
1:43
английского слова сид или начальное
1:46
значение его можно взять из шума или из
1:49
текущего времени в миллисекундах сид
1:52
используется в качестве входных данных
1:54
для простого действия например
1:56
возведем число в квадрат и из результата
1:59
возьмем средние цифры
2:00
повторяем и то же действие для нового
2:02
числа и так далее столько раз сколько
2:05
нужно
2:07
этот метод назвали серединных квадратов
2:10
он был первым из огромного множества
2:12
генераторов псевдослучайных чисел
2:17
вся последовательность зависит только от
2:19
начального значения
2:22
один и тот же сид означает ту же
2:24
последовательность и так в чем же
2:26
разница между случайными и псевдо
2:28
случайными последовательностями
2:30
изобразим каждую последовательность в
2:33
виде случайного блуждания
2:34
разницы не видно но давайте ускорим
2:37
процесс псевдослучайная
2:39
последовательность когда-нибудь
2:41
обязательно начнет повторяться это
2:43
произойдет когда некое число встретиться
2:45
и используется в качестве начального
2:48
значения во второй раз и цикл пойдет
2:50
заново длина такого цикла до его
2:53
повторения называется периодом
2:55
период строго ограничен размером сид
2:58
например если сид двузначное
3:00
то алгоритм выдаст максимум 100 чисел
3:02
после чего какое-то начальное значение
3:05
обязательно встретится повторно из
3:07
трехзначного сид нельзя получить больше
3:10
1000 чисел дальше алгоритму зациклиться
3:13
а из 4-значного сид нельзя получить
3:16
последовательность больше чем 10000
3:18
чисел но если взять достаточно большое
3:21
начальное значение
3:22
то алгоритм может выдать триллионы
3:25
триллионов знаков до того как возникнет
3:27
повтор и важно помнить ключевое отличие
3:30
при псевдо случайности генерации чисел
3:33
многие последовательности не выпадут
3:35
никогда например если или сгенерирует
3:38
действительно случайную
3:39
последовательность из 20 алфавитных
3:41
сдвигов это равносильно вытаскивание
3:44
случайного листа из стопки со всеми
3:47
возможными комбинациями
3:51
в этой стопке 26 в 20 степени листов это
3:55
астрономическое число если встать у
3:58
основания такой стопки и включить фонарь
4:00
человек наверху стопки увидят свет
4:02
только через двести миллионов лет
4:06
а если б или сгенерировала
4:08
псевдослучайная последовательность из
4:10
20-ти чисел при помощи 4-значного
4:13
начального значения
4:14
количество вариантов было бы ограничено
4:16
всего десятью тысячами различных
4:18
начальных сид
4:20
и она может сгенерировать лишь 10 тысяч
4:23
последовательностей и это ничтожно малая
4:26
доля от всех возможных
4:27
последовательностей
4:28
используя вместо случайных чисел
4:30
псевдослучайные
4:31
мы уменьшаем пространство ключей до
4:33
гораздо меньшего пространства начального
4:36
значения и чтобы псевдослучайная
4:38
последовательность была неотличима от
4:40
действительно случайный нужно чтобы
4:43
компьютер не смог перебрать все
4:44
возможные значения и не смог найти
4:47
совпадение и тут всплывает очень важное
4:50
различие между тем что возможно сделать
4:52
теоретически и тем что возможно сделать
4:55
за разумное время такая же логика у нас
4:57
появляется при покупке велосипедного
4:59
замка мы знаем что угонщик может
5:02
перебрать все возможные комбинации и
5:04
замок когда-нибудь откроется
5:06
но это может занять несколько дней для
5:09
псевдослучайных генераторов защита
5:11
возрастает с длиной начального значения
5:13
если какой-нибудь мощный компьютер будет
5:15
перебирать все возможные сид сотни лет
5:18
то мы можем положиться на достаточно
5:20
секретный шифр вместо совершенно
5:23
секретного но компьютеры становится
5:25
быстрее и размер начального значения
5:27
должен увеличиваться соответственно
5:29
псевдослучайный алгоритмы избавляет элис
5:32
и баба от необходимости передавать друг
5:34
другу длинные случайные цепочки вместо
5:37
этого они могут обменяться достаточно
5:39
коротким случайным начальным значением и
5:42
получить одну и ту же почти случайную
5:44
последовательность
5:46
но что случится если они не могут
5:48
встретиться и обменяться начальном
5:50
значения об этом мы поговорим в
5:52
следующих видео спасибо что
5:55
подписывайтесь на наш канал мы будем
5:57
рады услышать ваше мнение по поводу
5:59
этого видео если у вас возникли вопросы
6:01
касательно данного видеоролика
6:04
то напишите их в комментариях и мы с
6:06
удовольствием постараемся ответить на
6:08
них