Объясните чем отличаются случайные числа от псевдослучайных почему в компьютере
Обновлено: 07.07.2024
Решение
Псевдослучайные числа не являются действительно случайными числами, потому что они генерируются с использованием детерминированного процесса. Например, если бы я хотел получить случайное число от 0 до 4, и у меня был доступ к текущему времени в секундах, я мог бы генерировать псевдослучайные числа, применяя модуль 5 к значению времени, и это возвращало бы другое число от 0 до 4. Причина, по которой число не является действительно случайным, заключается в том, что его можно предсказать до генерации, зная время. По-настоящему случайное число никогда не может быть предсказано.
Другие решения
Этот вопрос может привести к очень глубокой философской кроличьей норе. Это открытый вопрос, действительно ли в природе существует процесс, который может быть действительно недетерминированным. Квантовая механика предполагает, что вселенная является недетерминированной, но с определенными вероятностными законами на некотором уровне. Тем не менее, это не исключает возможности того, что на каком-то более фундаментальном уровне находится детерминированный процесс, который просто кажется случайным, в более широком масштабе. Случайность и хаос тесно связаны, но они не обязательно означают одно и то же.
Генератор псевдослучайных чисел или PRNG использует алгоритм, который использует детерминированный хаос создать шаблон, который появляется статистически похож на истинный случайный процесс. PRNG обычно используют отправную точку или семя. Обычно для вывода PRNG используется выход функции времени. Существует множество разных алгоритмов для PRGN, которые отличаются по производительности и качеству.
Одним из существенных недостатков PRNG является то, что выходные данные в конечном итоге повторяются или являются периодическими. Также возможно, если кто-то знает алгоритм и отправную точку (семя), чтобы воссоздать точно такую же последовательность, потому что цифровые компьютеры обязательно являются детерминированными устройствами. Механизмы безопасности, основанные на PRNG, часто имеют скрытые уязвимости из-за используемых PRNG.
Некоторые приложения, особенно в области безопасности или, например, лотереи, требуют того, что в практических целях считается истинным генератором случайных чисел. Доступны аппаратные устройства, которые используют физические явления. Например, тепловой шум (то есть случайное движение электронов) определяется поведением квантовой механики и часто используется в аппаратных реализациях ГСЧ. Некоторые квантово-механические явления обычно считаются случайными. Согласно большинству стандартных интерпретаций квантовой механики, даже если бы у вас была полная модель системы (т.е. эволюция во времени уравнения Шредингера) и знание всех начальных переменных с бесконечной точностью, вы все равно не смогли бы предсказать точно следующее результат измерения.
Теоретически, вы также можете использовать радиопомехи (например, статический или радиошум между станциями). Любой из этих источников сигнала может быть отфильтрован или использован в качестве входных данных для PRNG для создания высококачественных случайных последовательностей без какой-либо заметной статистической предсказуемости.
Вот очень простой игрушечный алгоритм PRNG, с которым вы можете поиграть и помочь понять концепцию.
Вышеуказанное взято из Специальный простой генератор случайных чисел . Я надеюсь, что это проливает некоторый свет на ваш вопрос.
В чем разница между действительно случайным числом и псевдо
случайное число в C ++?
В C ++ можно повторять последовательность псевдослучайных чисел. «Действительно случайное» число (я думаю, что не поддерживается ни C ++, ни C, без специального оборудования) не может быть повторено.
Помечен как C ++, так что здесь есть один подход C ++.
В последнее время я использую то, что предоставляет C ++, но я все еще контролирую диапазон своих чисел, перетасовывая простой вектор значений. Это также поддерживает применение одного и того же случайного перемешивания более чем к одному тесту или для повторения последовательности.
Случайности преследуют нас всю жизнь и никогда не задумываешься, есть ли у нее какая-то формула или нет. Если обратиться к научной литературе, то можно прочитать такое вот определение случайности:
Настоящие случайные числа возможно генерировать измеряя случайные величины, которые называются шумом. В результате измерения шума в выборке и перевода его в числа, получается случайная числовая последовательность , которая никогда не повторится.
К примеру, если измерить статическое электричество от экрана телевизора, можно получить настоящую случайную последовательность.
Эту случайную последовательность легко визуализировать, построив путь, направление которого изменяется в зависимости от каждого числа.
Т.к. это - настоящая случайность, здесь мы не увидим ни одного повторяющегося шаблона.
Случайные процессы не детерминированы , ибо невозможно предсказать их поведение заранее.
Вычислительная техника, машины - детерминированы , т.к. операции, которыми они оперирую предсказуемы и повторяемы.
Тем не менее, на компьютерах также получают случайные числа , но они - менее случайны, или, скажем так, случайны, но не до конца - псевдослучайны .
В компьютере, псевдослучайные последовательности генерируются с помощью специальных алгоритмов и требуют для работы изначального числа.
Если попытаться визуализировать случайные и псевдослучайные последовательности чисел, то получится такая картина:
Отлично видно, что рано или поздно псевдослучайная последовательность начинает повторяться . Это происходит потому как алгоритм доходит до начального числа, которое использовалось для генерации последовательности и круг замыкается.
Начальное число последовательности или " Зерно " в компьютере берется из текущего времени или счетчика тактов процессора, или из иных мест, где можно получить хоть какую-то величину "случайно", а затем алгоритм генерирует последовательность. И чем больше зерно, тем больше чисел до начала повторения.
На данный момент, генерировать действительно случайные числа на компьютере довольно затруднительно. Даже измеряя какие-то физические величины, такие как шум звуковой карт, такты процесса, размер свободной памяти жесткого диска и другие, мы сильно теряем в производительности, потому, на выручку приходят псевдослучайные числа, которые генерируются куда быстрее.
Не могу понять в чем разница обычных чисел от псевдослучайных.
Можете показать на примере псевдослучайные числа и где их обычно применяют.
Тип обычных и случайных чисел один и тот же - number. В типе различия нет. То есть обычное число 5 и случайное число 5 - это то же самое, просто из контекста можно додуматься, что второе случайное.
Отличие в методе их получения и назначении. С обычными числами думаю и так понятно всё. А псевдо-случайные получаются различными методами, например Math.random() .
Нужны случайные числа например для случайного id или класса различным элементам (как постфикс у строк), как случайный идентификатор в широком применении, для обновления кэша в URL, для отрисовки графических точек в разной позиции, для генерации шумов и так далее.
То, что числа называются псевдо-случайными, а не случайными, означает то, что они получены алгоритмом, который не совсем случайный, и который теоретически или практически можно повторить с той же последовательностью.
Поскольку источники настоящей случайности найти непросто, в программировании обычно используются псевдослучайные числа, полученные детерминированным алгоритмом из некоторого начального значения (англ. seed). В случае хорошего генератора псевдослучайных чисел (ГПСЧ) полученная последовательность обладает теми же статистическими свойствами, что и последовательность настоящих случайных чисел. Однако никакой настоящей случайностью ГПСЧ не обладает: если взять то же самое начальное значение, на выходе получится та же самая последовательность псевдослучайных чисел.
Для примера, одним из самых простых методов генерации псевдослучайных чисел является линейный конгруэнтный метод, в котором последующее число получается из предыдущего умножением на a, добавлением c и вычислением остатка по модулю m, где a, c и m — специальным образом подобранные константы:
Псевдослучайные числа используются во многих областях, где требуются случайные числа, например, в компьютерных играх, моделировании, криптографии и т.д.
Компьютеры могут генерировать поистине случайные числа, наблюдая за некоторыми внешними данными, такими как движения мыши или шум вентилятора, который не предсказуем и создают данные из него. Это называется энтропией. В других случаях они генерируют «псевдослучайные» числа, используя алгоритм, поэтому результаты кажутся случайными, хотя таковыми не являются.
Эта тема становится всё более спорной в последнее время, и вызывает сомнение у большого количества людей. Чтобы понять, почему это может быть ненадежным, вам нужно понять, как используются случайные числа и для чего они нужны.
Как используют случайные числа
Случайные числа использовались в течение многих тысяч лет. Независимо от того, подкидывали ли монету или бросали кости, цель заключалась в том, чтобы получить случайный результат. Генераторы случайных чисел на компьютерах похожи – они пытаются достичь непредсказуемого случайного результата.
Генераторы случайных чисел полезны для разных целей. Помимо очевидных приложений, таких как генерация случайных чисел для азартных игр или создания непредсказуемых результатов в компьютерной игре, случайность важна для криптографии.
Истинные случайные числа
Возможно, вам интересно, как компьютер может генерировать случайное число. Откуда возникает эта «случайность». Если это всего лишь фрагмент компьютерного кода, возможно ли, что числа, которые генерирует компьютер, могут быть непредсказуемыми?
Обычно мы группируем случайные числа, создаваемые компьютером, в два типа, в зависимости от того, как они генерируются: «истинные» случайные числа и псевдослучайные числа.
Для генерации «истинного» случайного числа компьютер измеряет некоторый тип физического явления, которое происходит за пределами компьютера. Например, компьютер может измерять радиоактивный распад атома. Согласно квантовой теории, нет никакого способа точно знать, когда произойдет радиоактивный распад, так что это «чистая случайность». Злоумышленник не сможет предсказать, когда произойдет радиоактивный распад, поэтому они не будут знать случайное значение.
В бытовом случае компьютер может опираться на атмосферный шум или просто использовать точное время нажатия клавиш на клавиатуре в качестве источника непредсказуемых данных или энтропии. Например, ваш компьютер может заметить, что вы нажали клавишу ровно в 0,23423523 секунды после 2 часов дня. Это достаточный источник энтропии, который можно использовать для создания «истинного» случайного числа. Вы не предсказуемая машина, поэтому злоумышленник не сможет угадать точный момент, когда вы нажимаете эти клавиши.
Псевдослучайные числа
Псевдослучайные числа являются альтернативой «истинным» случайным числам. Компьютер может использовать начальное значение и алгоритм для генерации чисел, которые кажутся случайными, но которые, на самом деле, предсказуемы. Компьютер не собирает никаких случайных данных из среды.
Это не обязательно плохо. Например, если вы играете в видеоигру, не имеет значения, связаны ли события, происходящие в этой игре, с «истинными» случайными числами или псевдослучайными числами. С другой стороны, если вы используете шифрование, вряд ли Вам захочется использовать псевдослучайные числа, которые может угадать злоумышленник.
Например, злоумышленник знает алгоритм и начальное значение, которое использует генератор псевдослучайных чисел. Предположим, что алгоритм шифрования получает псевдослучайное число из этого алгоритма и использует его для генерации ключа шифрования без добавления дополнительной случайности. Если злоумышленник знает достаточно, он сможет «повернуть процесс вспять» и определять псевдослучайное число, вмешавшись в шифрование.
NSA и аппаратный генератор случайных чисел Intel
Чтобы упростить работу разработчиков и помочь генерировать безопасные случайные числа, чипы Intel включают аппаратный генератор случайных чисел, известный как RdRand. Этот чип использует источник энтропии на процессоре и предоставляет случайные числа для программного обеспечения, когда программное обеспечение запрашивает их.
Проблема здесь в том, что генератор случайных чисел – это, по сути, «черный ящик», и мы не знаем, что происходит внутри него. Если RdRand содержит бэкдор NSA, правительство сможет получить ключи шифрования, которые были сгенерированы с данными, предоставленными этим генератором случайных чисел.
Генератор случайных чисел — это намного сложнее, чем кажется.
Как думаете, что общего в компьютерных гонках, азартных играх и криптографии? На первый взгляд кажется, что ничего. Но на самом деле все они зависят от случайных чисел. От прослушивания музыки до шифрования всего Интернета — случайные числа являются важной частью жизни современного человека. И чаще всего мы полагаемся на компьютеры, которые генерируют их для нас.
Это заставляет задуматься: а как именно компьютеры генерируют случайные числа?
Если вы занимались программированием, то наверняка использовали в своем коде генератор случайных чисел. Для этого в Ruby достаточно вызвать «rand», а в Python — «random ()». Создание ряда случайных чисел может показаться простым. В конце концов числа на компьютере — это набор единиц и нулей. Машине просто нужно случайным образом выбрать 1 или 0 и повторить это столько раз, сколько нужно. Даже мы, люди, можем сделать это легко и просто на листе бумаги.
Однако если копнуть глубже, то мы создали компьютеры, чтобы стать теми, кем не являемся — полностью логическими устройствами. Получается, случайность противоречит их природе. Ну кто захочет, чтобы сервер спонтанно решил не следовать логике приложения?
По своей сути компьютеры — это простые машины, которые принимают данные и выводят их обратно. И чтобы эти машины могли генерировать случайные числа, им нужен внешний источник случайности. Этот источник будет зависеть от того, какой генератор случайных чисел вы захотите использовать. Таких генераторов два — конечно, если говорить об основных.
Первый и самый распространенный тип называется «генератор псевдослучайных чисел (ГПСЧ)». Как следует из названия, он не создает «истинных» случайных чисел. Чтобы сгенерировать с помощью него число, понадобится единственное начальное значение, откуда последует псевдослучайность. Алгоритмы генерации, используемые для ГПСЧ, включают в себя «метод извлечения квадратов», «линейный конгруэнтный метод», «регистр сдвига с линейной обратной связью» и «вихрь Мерсенна».
ГПСЧ автоматически создает длинные серии чисел с хорошими случайными свойствами и делает это быстро и дешево — в этом его преимущества. Но есть и очевидный минус: с ограниченными ресурсами любой ГПСЧ рано или поздно зацикливается и начинает повторять одну и ту же последовательность чисел. Однако чаще всего этот шаблон не воспринимается людьми, что делает ГПСЧ подходящим для использования в видеоиграх и программировании.
Нельзя не сказать о том, что слабым местом ГПСЧ все-таки пользуются: например, любители гонок, которые манипулируют ГСЧ и заставляют игру работать предсказуемо, чтобы пройти ее как можно скорее. Есть случаи, когда предсказание случайных чисел имеет более серьезные последствия. Зная начальное значение, злоумышленник может угадать сгенерированный пароль и получить доступ к личным данным пользователя.
Второй тип генератора — генератор «истинно» случайных чисел (ГИСЧ или TRNG). В качестве внешнего источника случайности он использует энтропию. Не углубляясь в теорию хаоса и термодинамику, отметим, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса — сам компьютер. Компьютер не может работать случайным образом, чего не скажешь о его составляющих.
Компьютер — это сложная система со множеством движущихся частей и непостоянством, где регулярно возникают тепловой шум, фотоэффект и другие квантовые явления. В конце концов инженеры по аппаратному обеспечению выяснили, что, используя сложную схему аппаратных микросхем и компонентов, компьютеры могут преобразовывать физический шум в цифровые единицы и нули.
Чаще всего ГИСЧ используют в цифровых азартных играх: бросание костей, тасование карт, рулетка — все это завязано на неопределенности. А еще в общественных вопросах, военных призывах и выборе присяжных, где случайность выступает в качестве метода справедливости.
Однако на самом деле спектр использования ГИСЧ тоже ограничен, ведь у него есть свои недостатки. Во-первых, для генерации чисел требуется много времени. А еще ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для создания истинных случайных чисел, но случайность заключается в том, что она возникает… случайно! Неактивный или новый сервер не сможет создавать номера такого же высокого качества, как активный.
Поскольку и ГПСЧ, и ГИСЧ имеют свои недостатки, их можно без проблем использовать в гейм-сфере и азартных играх, но нельзя — в криптографии, которая требует высокой безопасности. По этой причине появился гибридный тип — «криптографически стойкий генератор псевдослучайных чисел (КСГПЧ или CSPRNG)», который обладает скоростью ГПСЧ и безопасностью ГИСЧ.
КСГПЧ — это генератор, использующий высококачественный источник энтропии для создания начального числа. Затем оно вводится в алгоритм, который производит случайные и безопасные числа. Проще говоря, он использует ГИСЧ для создания начального числа для ГПСЧ. Если все сделано правильно, КСГПЧ гарантирует, что начальное число действительно случайно, а полученный результат нельзя взломать или реконструировать. Обычно его используют в операционных системах вроде Unix и Linux.
Тем не менее, даже несмотря на преимущества КСГПЧ, как и всего остального в технологической индустрии, абсолютная безопасность недостижима.
Теперь, когда в следующий раз вы будете играть в видеоигру, слушать музыку в случайном порядке или просто генерировать случайное число в своем коде, вы осознаете всю магию, которая творится «под капотом».
Читайте также: