Введение
Метод тестирования для проверки случайности генераторов псевдослучайных чисел. В криптографии и теории вычислений тест "следующего бита" является тестом для генераторов псевдослучайных чисел. Мы говорим, что последовательность битов проходит тест "следующего бита" в любой позиции последовательности, если любой злоумышленник, знающий первые биты (но не исходное значение), не может предсказать следующий бит с использованием разумной вычислительной мощности.
In cryptography and the theory of computation, the next bit test is a test against pseudo random number generators. We say that a sequence of bits passes the next bit test for at any position in the sequence, if any attacker who knows the first bits (but not the seed) cannot predict the st with reasonable computational power.
Точные заявления
Пусть P — многочлен, а S — коллекция множеств, таких что каждое множество содержит последовательности длиной n бит. Более того, пусть D — распределение вероятностей строк в S. Теперь определим следующий битовый тест двумя различными способами.
We now define the next bit test in two different ways.
Яо проверяет полноту
Следующий битовый тест является частным случаем теста Яо для случайных последовательностей, и успешное его прохождение, следовательно, является необходимым условием для успешного прохождения теста Яо. Однако, Яо также показал, что это условие достаточно. Мы докажем это сейчас для случая вероятностной машины Тьюринга, поскольку Адлеман уже выполнил работу по замене рандомизации неравномерностью в своей теореме. Случай булевых схем нельзя вывести из этого случая (поскольку он предполагает решение потенциально неразрешимых задач), но доказательство теоремы Адлемана можно легко адаптировать к случаю неравномерных семейств булевых схем. Пусть – это различитель для вероятностной версии теста Яо, то есть вероятностная машина Тьюринга, работающая за полиномиальное время, такая, что существует полином такой, что для бесконечного числа
Пусть у нас есть: и
Тогда мы замечаем, что, следовательно, по крайней мере одно из должно быть не меньше, чем
Далее рассмотрим распределения вероятностей и на Распределение определяет вероятность выбора первых битов в с вероятностью, заданной , а оставшиеся биты выбираются равномерно случайно. Таким образом, мы имеем:
Then, we notice that Therefore, at least one of the should be no smaller than
Next, we consider probability distributions and on Distribution is the probability distribution of choosing the first bits in with probability given by , and the remaining bits uniformly at random. We have thus:
Таким образом, мы имеем (это показывает простой математический трюк), следовательно, распределения и можно различить. Без потери общности можно предположить, что , где – полином. Это дает нам возможную конструкцию машины Тьюринга, решающей следующий битовый тест: получив первые бита последовательности, она дополняет этот ввод предположением о бите и затем случайными битами, выбранными с равномерной вероятностью. Затем она запускает , и выводит , если результат равен , и в противном случае.