Почему мы не объединяем генераторы случайных чисел?

60

Существует множество приложений, в которых используется генератор псевдослучайных чисел. Поэтому люди реализуют то, что, по их мнению, замечательно, но потом обнаруживают, что оно ошибочно. Нечто подобное произошло с генератором случайных чисел Javascript в последнее время. RandU намного раньше тоже. Есть также проблемы неподходящего начального посева для чего-то вроде Twister.

Я не могу найти примеров того, как кто-нибудь объединял два или более семейств генераторов с обычным оператором xor. Если у компьютера достаточно мощности для запуска таких вещей, как реализации java.SecureRandom или Twister, почему люди не объединяют их? ISAAC xor XORShift xor RandU должен быть довольно хорошим примером, где вы можете увидеть слабость одного генератора, смягчаемую другими. Это также должно помочь с распределением чисел в более высокие измерения, поскольку внутренние алгоритмы совершенно разные. Есть ли какой-то фундаментальный принцип, что их не следует объединять?

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

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

Пол Ушак
источник
Ответ может зависеть от приложения. Для чего вы хотите использовать псевдослучайную последовательность?
Юваль Фильмус
1
Нашли ли вы, что Fortuna ( en.wikipedia.org/wiki/Fortuna_%28PRNG%29 ) звучит так, как будто она близка к тому, что вы описываете, что она объединяет различные случайные источники в один.
Небольшой код
1
@LittleCode На самом деле это звучит совсем по-другому. Fortuna выводит данные из одной хэш-функции. Это просто мешает с множеством слабых механизмов сбора энтропии, прежде чем (пере) хешировать его через единственную функцию вывода. Мой вопрос связан с выводом из нескольких функций (почему не 10 из них)? Если это заполняющее устройство, скорость все равно не имеет значения.
Пол Ушак,
1
Покойный Джордж Марсаглия, известный исследователь в области PRNG, который изобрел множество новых типов PRNG, таких как «умножение с переносом» и «смещение по оси X», сделал именно это, предложив в 1990-х годах генератор KISS, представляющий собой комбинацию из трех PRNG. разного типа. Последние двадцать лет я успешно использую KISS, конечно, не для криптографии. Полезный вторичный источник в отношении KISS - это статья Грега Роуза 2011 года, в которой он указывает на проблему с одним из составляющих PRNG, которая не лишает законной силы концепцию объединения
njuffa
4
Кнут связывает результат наивного объединения генераторов псевдослучайных чисел (используя одно случайное число, чтобы выбрать, какой генератор использовать), что приводит к функции, которая сходится к фиксированному значению! Итак, еще до революции микрокомпьютеров он предупредил нас, чтобы мы никогда не смешивали случайные генераторы.
JDługosz

Ответы:

7

IIRC (и это по памяти), бестселлер Rand 1955 года A Million Random Digits сделал нечто подобное. Прежде чем компьютеры стали дешевыми, люди выбирали случайные числа из этой книги.

Авторы генерировали случайные биты с электронным шумом, но это оказалось смещением (трудно сделать триггер, потраченный ровно столько же раз на триггер и флоп). Однако объединение битов сделало распределение намного более равномерным.

любительский
источник
45

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

На практике, если у вас есть потребность в очень высококачественном PRNG, вы используете хорошо проверенный PRNG с криптографической стойкостью, и вы засеиваете его истинной энтропией. Если вы сделаете это, ваш наиболее вероятный режим сбоя не является проблемой самого алгоритма PRNG; наиболее вероятный режим отказа - отсутствие адекватной энтропии (или, возможно, ошибки реализации). Использование нескольких PRNG не помогает в этом режиме отказа. Так что, если вы хотите очень качественный PRNG, вероятно, нет смысла их хранить.

В качестве альтернативы, если вам нужен статистический PRNG, который достаточно хорош для целей моделирования, обычно проблемой № 1 является либо скорость (очень быстрое генерирование псевдослучайных чисел), либо простота (не нужно тратить много времени на разработку или исследование). Xoring замедляет PRNG и делает его более сложным, поэтому он также не отвечает основным потребностям в этом контексте.

Пока вы проявляете разумную заботу и компетентность, стандартные PRNG более чем достаточно хороши, поэтому на самом деле нет никаких причин, по которым нам нужно что-то более изощренное (не нужно делать xor-ing). Если у вас нет даже минимального уровня обслуживания или компетенции, вы, вероятно, не собираетесь выбирать что-то сложное, например, занятие хорингом, и лучший способ улучшить ситуацию - это сосредоточиться на большей заботе и компетентности при выборе PRNG. а не на xor-ing.

Итог : по сути, трюк xor не решает проблемы, которые обычно возникают у людей при использовании PRNG.

DW
источник
3
«нехватка адекватной энтропии ... ксерокопирование нескольких PRNG не поможет с этим» - действительно, это может помешать, поскольку вы увеличиваете количество энтропии, необходимое для заполнения ваших PRNG. Вот почему вы не хотите, чтобы обычные практики объединяли хорошо проверенные PRNG, даже если они действительно защищают вас от одного из этих проверенных PRNG, которые оказываются полным мусором (в используемой вами реализации) ,
Стив Джессоп
Другая причина заключается в том, что ошибки реализации гораздо, гораздо чаще встречаются, чем фундаментальные проблемы с алгоритмами, поэтому чем проще, тем лучше. Стандартный алгоритм может быть, по крайней мере, протестирован с другой реализацией или ссылочными значениями, а пользовательский xor не может.
Жиль "ТАК - перестань быть злым"
1
@DW Почему "сеял самостоятельно?" Поскольку мой вопрос касается комбинаций разных семейств генераторов, каждое семейство должно создавать уникальную выходную последовательность из одинаковых семян. Например, java.SecureRandom и RC4 могут быть легко выделены из одного и того же ключа, а затем объединены.
Пол Ушак
1
@DW Большое предположение, которое вы заявляете: «используйте проверенный PRNG с криптографической стойкостью». Реальность такова, что это практически невозможно установить, так как с большинством криптографических шифров, хэшей и т. Д. Со временем обнаруживаются слабые места. Они были "хорошо проверены" на знание вчерашнего или прошлых лет.
Шив
1
@PaulUszak, я не думаю, что когда-либо утверждал, что использование двух генераторов делает его более подверженным ошибкам. Я говорю, что если вы выберете хороший PRNG (только один), один из наиболее вероятных режимов сбоя - сбой заполнения или сбой реализации, и перенос двух генераторов не поможет ни с одним из них. (Конечно, если один PRNG не выходит из строя, то пересылка двух генераторов также бесполезна.) Таким образом, в основном это решение неправильной проблемы. Другими словами, xor-генераторы не сильно повышают достоверность, потому что не устраняют наиболее важные причины неопределенности.
DW
19

Фактически, что-то о прорыве было только что объявлено, сделав именно это.

Профессор информатики Техасского университета Дэвид Цукерман и аспирант Эшан Чаттопадхьяй обнаружили, что «высококачественное» случайное число может быть получено путем объединения двух «некачественных» случайных источников.

Вот их статья: Явные экстракторы с двумя источниками и упругие функции

NietzscheanAI
источник
8
Это чисто теоретическая статья на другую тему, которая не имеет абсолютно никакого практического значения, несмотря на пиар-усилия UT.
Юваль Фильмус
4
@Yuval Filmus - не могли бы вы расширить этот комментарий?
NietzscheanAI
8
Существует большая пропасть между теорией и практикой. Обычно практикующих не волнует теория, и наоборот. В этом случае пиар-отдел UT решил воспользоваться отличной теоретической статьей, назвав ее практически актуальной, а это не так. Проблемы, рассмотренные в статье, не столь интересны с практической точки зрения и имеют простые решения, которые работают достаточно хорошо, хотя доказать это невозможно.
Юваль Фильмус
2
Более того, этот конкретный документ является лишь одной работой в теоретической области экстракторов. Вы можете выставить счет любой другой бумаге в этой области таким же образом. Они все о соединении слабых источников, чтобы создать сильный источник. Разница только в параметрах.
Юваль Фильмус
3
Наконец, конструкция в документе, скорее всего, является излишним, а не тем, что вы бы хотели реализовать. Конкретные параметры для этого типа конструкции трудно определить, и они, как правило, крайне плохие, поскольку статьи всегда фокусируются на асимптотическом режиме и игнорируют константы.
Юваль Фильмус
9

Предположим, что - псевдослучайная двоичная последовательность. То есть каждый X i является случайной величиной, поддерживаемой в { 0 , 1 } , а переменные X 1 , , X n не обязательно являются независимыми. Мы можем думать о том, что эта последовательность генерируется следующим образом: сначала мы выбираем равномерно случайный ключ K , а затем используем некоторую функцию f ( K )X1,,XnXi{0,1}X1,,XnKf(К) для генерации псевдослучайной последовательности.

Как измерить, насколько хороша псевдослучайная последовательность ? Хотя можно измерить, насколько хороша конкретная реализация (скажем, с помощью колмогоровской сложности), здесь я сосредоточусь на мерах, которые зависят от всего распределения случайной величины ( X 1 , , X n ) . Одним из таких примеров является энтропия, но нам потребуются только два свойства нашей меры L : (большее L ( ) означает более случайную последовательность)Икс1,...,ИксN(Икс1,...,ИксN)LL()

  • Если Y1,...,YN является детерминированной последовательности (то есть, фиксированная последовательность) , то .L(Икс1Y1,...,ИксNYN)знак равноL(Икс1,...,ИксN)

  • Если - две независимые псевдослучайные последовательности, T { 0 , 1 } - независимый случайный бит, и Z = X TИкс0,Икс1T{0,1}Zзнак равноИксT , то .L(Z)мин(Икс0,Икс1)

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

Любая разумная мера случайности будет удовлетворять первому свойству. Второе свойство удовлетворяется наиболее популярными мерами, такими как энтропия и минимальная энтропия H .ЧАСЧАС

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

Теорема. Пусть - две независимые псевдослучайные последовательности одинаковой длины, и пусть LИкс,YL - допустимая мера случайности (одна удовлетворяет двум вышеуказанным условиям). Тогда

L(ИксY)Максимум(L(Икс),L(Y)),

Доказательство. Предположим, что . Тогда X Y является смесью распределений X y , смешанных по распределению YL(Икс)L(Y)ИксYИксYY . Поскольку и смесь, по крайней мере, так же хороша, как и наихудшее распределение при смешивании, мы получаем L ( X Y ) L ( X ) . L(ИксY)знак равноL(Икс)L(ИксY)L(Икс) 

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

На практике, чтобы использовать два независимых ключа, мы, вероятно, расширяем один ключ до двух ключей псевдослучайным образом. Эти два ключа не являются независимыми. Однако, если мы используем «дорогой» способ расширения одного ключа на два ключа, мы ожидаем, что полученные два ключа будут «выглядеть» независимыми, и поэтому теорема будет «морально». В теоретической криптографии есть способы сделать это утверждение точным.


Должны ли мы тогда XOR два генератора псевдослучайных чисел? Если мы не ограничены скоростью, то это, безусловно, хорошая идея. Но на практике у нас есть ограничение скорости. Затем мы можем задать следующий вопрос. Предположим, что нам даны два PRNG, каждый с параметром который управляет временем работы (и, следовательно, мощностью) генератора. Например, T может быть длиной LFSR или количеством раундов. Предположим, что мы используем один PRNG с параметром T 1 , другой с параметром T 2 и XOR результат. Можно предположить, что T 1 + T 2 = t , так что общее время работы постоянно. Какой лучший выборTTT1T2T1+T2знак равноTT1,T2 ? Здесь есть компромисс, на который сложно ответить вообще. Может случиться так, что настройка намного хуже, чем ( t , 0 ) или ( 0 , t ) .(T/2,T/2)(T,0)(0,T)

Лучший совет здесь - придерживаться популярного PRNG, который считается сильным. Если вы можете сэкономить больше времени для генерации своей последовательности, сделайте XOR несколько копий, используя независимые ключи (или ключи, сгенерированные путем расширения одного ключа с использованием дорогого PRNG).

Юваль Фильмус
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат . Как только вы придете к конструктивному концу, пожалуйста, отредактируйте ответ, чтобы включить результаты вашего обсуждения.
Рафаэль
4

Я дам этому шанс, так как я достаточно обеспокоен советом, данным в некоторых других ответах.

Пусть - бесконечные битовые последовательности, сгенерированные двумя RNG (не обязательно PRNG, которые являются детерминированными после того, как известно начальное состояние), и мы рассматриваем возможность использования последовательности XY с надеждой на улучшение поведения в каком-то смысле. Есть много разных способов, которыми XY можно считать лучше или хуже по сравнению с каждым из X и Y ; Вот небольшая горстка, которая, я считаю, имеет смысл, полезна и согласуется с обычным употреблением слов «лучше» и «хуже»:Икс,YИксYИксYИксY

  • (0) Вероятность истинной случайности последовательности увеличивается или уменьшается
  • (1) Вероятность наблюдаемой неслучайности увеличивается или уменьшается (по отношению к некоторому наблюдателю, применяющему определенное количество проверки, предположительно)
  • (2) Степень / очевидность наблюдаемой неслучайности увеличивается или уменьшается.

Икс,YεИкс,εYИксYεИксεY<мяN{εИкс,εY}εИкс,εYИкс,Y

пр(ИксY NоT TрULY рaNdом)мин{пр(Икс NоT TрULY рaNdом),пр(Y NоT TрULY рaNdом),пр(Икс,Y dепеNdеNT)},
Поэтому мы можем заключить, что в смысле (0) XOR не может причинить вреда и потенциально может сильно помочь.

Однако (0) не представляет интереса для PRNG, поскольку в случае PRNG ни одна из рассматриваемых последовательностей не имеет шансов быть действительно случайной.

Поэтому для этого вопроса, который на самом деле касается PRNG, мы должны говорить о чем-то вроде (1) или (2). Так как они с точки зрения свойств и величин, таких как «наблюдаемый», «серьезный», «очевидный», «очевидный», мы сейчас говорим о колмогоровской сложности, и я не буду пытаться уточнить это. Но я пойду настолько далеко, что сделаю, надеюсь, неоспоримое утверждение, что с помощью такой меры «01100110 ...» (период = 4) хуже, чем «01010101 ...» (период = 2), что хуже, чем « 00000000 ... "(постоянный).

ИксYИксYИксзнак равноYИксзнак равноNоT(Y)ИксYИксYИксYИксY

Такая неожиданная зависимость оказывается действительно большой проблемой.


Пример того, что идет не так

Вопрос гласит: «Я исключаю общий пример нескольких регистров сдвига с линейной обратной связью, работающих вместе, поскольку они принадлежат к одному семейству». Но я собираюсь на время исключить это исключение, чтобы привести очень простой и понятный пример из жизни, который может пойти не так с XORing.

Моим примером будет старая реализация rand (), которая была в какой-то версии Unix около 1983 года. IIRC, эта реализация функции rand () имела следующие свойства:

  • значение каждого вызова rand () составляло 15 псевдослучайных битов, то есть целое число в диапазоне [0, 32767).
  • последовательные возвращаемые значения чередуются четно-нечетно-четно-нечетно; то есть младший значащий бит чередуется 0-1-0-1 ...
  • 215
  • поэтому последовательность 15-битных возвращаемых значений rand () была периодической с периодом 215

Мне не удалось найти исходный исходный код, но я предполагаю, что собрав воедино пару постов из https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A, которые он сделал именно следующее (код C), что согласуется с моей памятью о свойствах выше:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Как можно себе представить, попытка использовать этот rand () различными способами привела к целому ряду разочарований.

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

rand() & 1

яя-1 «бесполезно» здесь; все, что мы действительно можем сказать, это то, что пронумерованные позиции битов были различной степени полезности / бесполезности.

Я также пробовал такие вещи, как дальнейшее скремблирование результатов или объединение значений XOR, возвращаемых из нескольких вызовов rand (). Конечно, XOR для пар последовательных значений rand () был катастрофой - он приводил ко всем нечетным числам! Для моих целей (а именно, для создания «очевидно случайной» последовательности бросков монет) результат XOR с постоянной четностью был даже хуже, чем чередующееся четно-нечетное поведение оригинала.

ИксsИксYsYИксY будет последовательностью либо всех четных, либо полностью нечетных чисел, что хуже, чем исходное чередующееся четное / нечетное поведение.

Другими словами, это пример, когда XOR ухудшил ситуацию в смысле (1) и (2), с помощью любой разумной интерпретации. Хуже и в нескольких других отношениях:

  • (3) младший значащий бит XOR явно смещен, то есть имеет неравные частоты 0 и 1, в отличие от нумерованного положения бита на любом из входов, которые все несмещены.
  • (4) На самом деле, для каждой позиции бита есть пары начальных чисел, для которых эта позиция бита смещена в результате XOR, и для каждой пары начальных чисел существуют (по крайней мере 5) позиции битов, которые смещены в XOR результат.
  • 214215 для оригиналов.

Ни одно из (3), (4), (5) не является очевидным, но все они легко проверяемы.


Наконец, давайте рассмотрим повторное введение запрета на PRNG из одной семьи. Проблема здесь, я думаю, заключается в том, что никогда не ясно, являются ли два PRNG «одного и того же семейства», до тех пор, пока / если кто-то не начнет использовать XOR и не заметит (или не заметит злоумышленник), что вещи стали хуже в смысле (1) и (2), то есть до тех пор, пока неслучайные паттерны в выходных данных пересекают порог от незамеченного к заметному / смущающему / катастрофическому, и в этот момент уже слишком поздно.

Я встревожен другими ответами здесь, которые дают безоговорочный совет «XOR не может навредить» на основе теоретических мер, которые, как мне кажется, плохо справляются с моделированием того, что большинство людей считают «хорошим» и «плохим» в отношении PRNGs в реальной жизни. Этот совет противоречит ясным и вопиющим примерам, в которых XOR ухудшает ситуацию, например, приведенному выше примеру rand (). Хотя вполне возможно, что относительно «сильные» PRNG могли последовательно отображать противоположное поведение, когда XORed к поведению игрушечного PRNG, который был rand (), тем самым делая XOR хорошей идеей для них, я не видел никаких доказательств в этом направлении, теоретических или эмпирически, поэтому мне кажется необоснованным предполагать, что это происходит.

Лично, будучи застигнутым врасплох XORing rand () в моей юности и бесчисленными другими неожиданными корреляциями в течение всей моей жизни, у меня нет особых оснований полагать, что результат будет другим, если я попробую подобную тактику снова. Вот почему я лично очень неохотно делаю XOR вместе с несколькими PRNG, если только не был проведен очень тщательный анализ и проверка, чтобы дать мне некоторую уверенность в том, что это может быть безопасно сделать для конкретных рассматриваемых RNG. Как потенциальное лекарство от того, когда у меня низкая уверенность в одном или нескольких отдельных PRNG, их XOR вряд ли увеличит мою уверенность, поэтому я вряд ли буду использовать его для этой цели. Я полагаю, что ответ на ваш вопрос заключается в том, что это широко распространенное мнение.

Дон хэтч
источник
Так как же объяснить использование A5 / 1 буквально миллиардами людей?
Павел Ушак,
@PaulUszak Понятия не имею. Противоречит ли A5 / 1 миллиардам людей тому, что я сказал?
Дон Хэтч
Это три prngs (на самом деле из одной семьи), соединенные вместе, чтобы создать лучший способ, который мешает и тревожит вас ...
Paul Uszak
Что меня беспокоит и встревоживает, так это безоговорочный совет: «Если вы не уверены, продолжайте и сделайте XOR вместе с группой RNG; это не может ухудшить ситуацию». Я не хотел сказать или подразумевать, что XOR плох во всех случаях, и у меня нет никакого мнения о A5 / 1 или использовании XOR в нем. Поможет ли мне изменить мое окончательное глупое резюме, чтобы сделать это более понятным?
Дон Хэтч
1
В конце я заменил упрощенное «просто скажи нет XORing RNG» на что-то более реальное и, надеюсь, менее вводящее в заблуждение.
Дон Хэтч
0

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Этот ответ строго о «мы не делаем это», а не «вот математическое доказательство того, почему он может или не может работать». Я не утверждаю, что XOR вводит (или нет) какие-либо криптографические уязвимости. Моя точка зрения заключается лишь в том, что опыт показывает нам, что даже самые простые схемы почти всегда приводят к непредвиденным последствиям, и именно поэтому мы их избегаем.

«Случайность» - это лишь верхушка айсберга, когда речь заходит о ГСЧ и ГСЧ. Есть и другие важные качества, например, однородность.

Представьте себе обычную игру в кости, которая сама по себе является неплохой ГСЧ. Но теперь допустим, что вам нужен диапазон 1-5 вместо 1-6. Первое, что приходит на ум, - это просто стереть лицо 6 и заменить его дополнительным 1. «Случайность» сохраняется (результаты по-прежнему действительно случайны), однако единообразие сильно страдает: теперь 1 в два раза чаще, чем другие результаты.

Объединение результатов от нескольких ГСЧ является аналогичным скользким уклоном. Например. простое добавление бросков в 2 кубика полностью уничтожает любую однородность, поскольку «7» теперь в 6 раз чаще, чем «2» или «12». Я согласен, что XOR выглядит лучше, чем сложение на первый взгляд, но в PRNG ничего не получается, как выглядит на первый взгляд.

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

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

Agent_L
источник
7
Сильно не согласен. Если вы XOR действительно случайная последовательность с произвольной последовательностью, вы все равно получите действительно случайную последовательность. Точно так же, если вы XOR две независимые псевдослучайные последовательности (то есть, сгенерированные с различными ключами), вы получите что-то по крайней мере так же сильные, как каждая в отдельности.
Юваль Фильмус
3
Это кажется мне неправильным. Обычным случаем здесь является то, что я думаю, что у меня есть два очень высококачественных ГСЧ, которые производят по существу действительно случайные биты, но есть небольшой шанс, что я могу (возможно, грубо) ошибиться в одном (или, гораздо реже, в обоих) из них. Если я сделаю их вместе, пока я прав по крайней мере по одному из них, результат будет действительно случайным, и я в порядке. Таким образом, комбинируя их, я уменьшил свой шанс получить плохую ГСЧ с примерно эпсилона / 2 до чрезвычайно крошечного эпсилона ^ 2, что, безусловно, является победой. Я подозреваю, что подобная динамика сохраняется даже в менее практичных случаях.
Дон Хэтч
2
Я до сих пор не убежден. Когда я писал «действительно случайный», я имел в виду «равномерно случайный». Если вы XOR равномерно случайной последовательности с произвольной последовательностью, вы получите равномерно случайную последовательность.
Юваль Фильмус
2
Pr[Икся+100знак равноИкся]знак равно(1+ε)/2Zязнак равноИксяYяPr[Zя+100знак равноZя]знак равно(1+ε2)/2ε2|ε|
3
@YuvalFilmus Вы, вероятно, правы, что соотношение между предметом i и предметом i + 100 сильно уменьшилось, но это не главное. Для очень конкретного и реального примера: я помню, что старая реализация crappy rand () в unix имела периодическое поведение в младшем бите каждого возвращаемого 31-битного целого числа, которое большинство людей не замечали. Скопировав эту последовательность целых чисел со смещенной копией самого себя (что получается при использовании другого начального числа) неудачного размера сдвига, вы получите все четные числа. Это намного хуже, чем проблема в исходной последовательности, для большинства целей.
Дон Хэтч