Генератор псевдослучайных чисел — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению.
Комбинато́рика — раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций являются перестановки, сочетания и размещения.
Веще́ственное число́ — математический объект, возникший из потребности измерения геометрических и физических величин окружающего мира, а также проведения таких вычислительных операций, как извлечение корня, вычисление логарифмов, решение алгебраических уравнений, исследование поведения функций.
Медиа́на, или серединное значение набора чисел — число, которое находится в середине этого набора, если его упорядочить по возрастанию, то есть такое число, что половина из элементов набора не меньше него, а другая половина не больше. Другое равносильное определение: медиана набора чисел — это число, сумма расстояний от которого до всех чисел из набора минимальна. Это определение естественным образом обобщается на многомерные наборы данных и называется 1-медианой.
Вихрь Мерсе́нна — генератор псевдослучайных чисел (ГПСЧ), алгоритм, разработанный в 1997 году японскими учёными Макото Мацумото и Такудзи Нисимура. Вихрь Мерсенна генерирует псевдослучайные последовательности чисел с периодом, равным одному из простых чисел Мерсенна, отсюда этот алгоритм и получил своё название, и обеспечивает быструю генерацию высококачественных по критерию случайности псевдослучайных чисел.
Псевдослуча́йная двои́чная после́довательность — частный случай псевдослучайной последовательности, в которой элементы принимают два возможных значения 0 и 1. Является периодической.
Аппара́тный генера́тор случа́йных чи́сел (генератор истинно случайных чисел) — устройство, которое генерирует последовательность случайных чисел на основе измеряемых, хаотически изменяющихся параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных источников энтропии, таких, как тепловой шум, дробовой шум, фотоэлектрический эффект, квантовые явления и т. д. Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные числа проверяются с помощью специальных статистических тестов.
Тестирование псевдослучайных последовательностей — совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п.
Статистические тесты NIST — пакет статистических тестов, разработанный Лабораторией информационных технологий, являющейся главной исследовательской организацией Национального института стандартов и технологий (NIST). В его состав входят 15 статистических тестов, целью которых является определение меры случайности двоичных последовательностей, порождённых либо аппаратными, либо программными генераторами случайных чисел. Эти тесты основаны на различных статистических свойствах, присущих только случайным последовательностям.
Криптографически стойкий генератор псевдослучайных чисел — это генератор псевдослучайных чисел с определёнными свойствами, позволяющими использовать его в криптографии.
Регистр сдвига с обобщённой обратной связью — вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Теодором Льюисом и Уильямом Пейном в 1973 году.
Тест на следующий бит — тест, служащий для проверки генераторов псевдо-случайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.
Алгоритм Блюма — Микали — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна. Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного алгоритма являются биты, а не числа.
Случайные числа — искусственно полученная последовательность реализаций случайной величины с заданным законом распределения.
Случайная перестановка — это случайное упорядочение множества объектов, то есть случайная величина, элементарными событиями которой являются перестановки. Использование случайных перестановок зачастую является базой в областях, использующих рандомизированные алгоритмы. К таким областям относятся теория кодирования, криптография и моделирование. Хорошим примером случайной перестановки является тасование колоды карт.
TestU01 — это пакет статистических эмпирических тестов, реализованный на языке ANSI C, который предлагает набор утилит для тестирования генераторов случайных чисел. Последняя версия библиотеки была представлена в 2007 году Пьером Л`Экуйе и Ричардом Симардом из Монреальского университета.
Экстрактор случайности — функция, которая применяется к выходу из слабо случайного источника энтропии, вместе с коротким равномерно распределённым случайным начальным значением и генерирует случайный выход, который выглядит независимым от источника и равномерно распределён. Примерами слабо случайных источников могут быть радиоактивный распад или тепловой шум. Единственное ограничение на возможные источники состоит в том, что не должно быть никакого способа, которым они могут полностью контролироваться, рассчитываться или предсказываться, таким образом, чтобы могла быть установлена нижняя граница для их уровня энтропии. Для данного источника экстрактор случайности может даже считаться истинным генератором случайных чисел, тем не менее нет единственного экстрактора, который, как доказывали, производил бы действительно случайный выход из любого типа слабо случайного источника.
Xorshift — класс генераторов псевдослучайных чисел, открытых Джорджем Марсалья. Генераторы такого типа представляют собой подмножество регистров сдвига с линейной обратной связью (LFSR), что позволяет эффективно реализовать их без чрезмерного использования разреженных многочленов. Генерация следующего числа в последовательности происходит путём многократного вычисления исключающее «ИЛИ» текущего числа и его битового сдвига, что делает xorshift чрезвычайно быстрыми на современных компьютерных архитектурах. Как и все LFSR, xorshift требуют тщательного подбора начальных параметров, для получения более длинных периодических последовательностей.
Критерий Вальда — Вольфовица, названный в честь статистиков Абрахама Вальда и Джейкоба Вольфовица, представляет собой непараметрический статистический тест, который проверяет гипотезу о случайности для двух последовательностей данных одинаковой длины. Точнее, данный критерий можно использовать для проверки нулевой гипотезы о том, что элементы двух последовательностей взаимно независимы.
В математике и информатике метод средних квадратов — это метод генерации псевдослучайных чисел. Метод имеет непоправимые недостатки для многих практических применений, так как его период обычно очень короткий, а также: после некоторого количества итераций либо начнётся повторное генерирование одного и того же числа, либо последовательность зациклится на предыдущем числе.