Предположим я генерирую неотрицательное число x1 из 64 битов неким псевдорандомным генератором. Далее я генерирую число x2 из 64 битов в цикле, пока оно не станет больше числа x1. Далее я генерирую число x3 больше x2 и так далее. И так генерирую чисто xn. Предположим, что мне это удалось, т.е. ситуацию, когда очередной xi равен 2^64 — 1 не рассматриваем.
Некая энтропия (не уверен, что правильно пользуюсь этим термином) для x1 очевидно равна 64 бита. Т.е. имеется 2^64 вариантов.
Чему равна энтропия для xn при таком алгоритме?
Интуитивно кажется, что 64 — n + 1. Но хочется быть уверенным.
Re: Уменьшение энтропии при генерации числа больше предыдущего
Здравствуйте, vsb, Вы писали:
vsb>Предположим я генерирую неотрицательное число x1 из 64 битов неким псевдорандомным генератором. Далее я генерирую число x2 из 64 битов в цикле, пока оно не станет больше числа x1. Далее я генерирую число x3 больше x2 и так далее. И так генерирую чисто xn. Предположим, что мне это удалось, т.е. ситуацию, когда очередной xi равен 2^64 — 1 не рассматриваем.
vsb>Некая энтропия (не уверен, что правильно пользуюсь этим термином) для x1 очевидно равна 64 бита. Т.е. имеется 2^64 вариантов.
Какая энтропия? Вовсе не очевидно, что она равна 64 бита. Зависит, например, от псевдорандомного генератора. Вообще, определений разных куча, так что определяй.
vsb>Интуитивно кажется, что 64 — n + 1. Но хочется быть уверенным.
Можно сгенерировать 100 чисел таким методом, и тогда 64-100+1 < 0. Отрицательной энтропии не бывает.
Re[2]: Уменьшение энтропии при генерации числа больше предыд
Здравствуйте, Sharowarsheg, Вы писали:
vsb>>Некая энтропия (не уверен, что правильно пользуюсь этим термином) для x1 очевидно равна 64 бита. Т.е. имеется 2^64 вариантов.
S>Какая энтропия? Вовсе не очевидно, что она равна 64 бита. Зависит, например, от псевдорандомного генератора. Вообще, определений разных куча, так что определяй.
Генератор будем считать рандомным.
Ну можно так определить. Пусть есть злоумышленник, который хочет подобрать это число. Если это x1, то ему надо перебрать числа и в среднем ему понадобится 2^63 попыток. Для xn очевидно перебирать нужно с конца (можно переформулировать задачу зеркально отразив для упрощения рассуждений). То бишь надо определить, сколько в среднем понадобится попыток злуомышленнику, чтобы найти число xn.
Если заменить формулировку задачи с 64 на 8 битов, n = 2, x2 < x1. Получается, что x1 генерируется от 1 до 255 (0 опускаем, чтобы не было ситуации с невозможным x2). Для каждого равновероятного x1 от 1 до 255 рассматриваем равновероятные x2 от 0 до (x1 — 1). Далее находим среднее арифметическое всех таких x2 и это кажется будет тем самым числом попыток (минус один), с которых в среднем злоумышленник будет угадывать x2, перебирая с 0. Получается [(0) + (0 + 1) + (0 + 1 + 2) + ... + (0 + ... + 254)] / (1 + 2 + ... + 255) = [0 * 1 / 2 + 1 * 2 / 2 + 2 * 3 / 2 + ... + 254 * 255 / 2] / [(1 + 255) * 255 / 2] = [\sum_{i = 0}^{254} i * (i + 1) / 2] / (256 * 255 / 2)
Как это посчитать я не знаю. Если просто посчитать — получится 84.(6). То бишь на подбор первого числа в среднем нужно 128 попыток, на подбор второго — 85.(6) попытки. Если я нигде не напутал. Ну да — явно не минус один бит.
Для n = 3 и 8 битов получается 63.25, для 4 битов получается 50.4. Это я просто перебором сделал. В принципе формула очевидная — (256 — n) / (n + 1). Хм. Сам решил что-ли, методом подбора. Если так, то выходит, что от исходного числа битов "энтропии" отнимается примерно log2(n) битов (ну там +-1, лень думать). То бишь если вернуться к исходной постановке задачи, то можно сгенерировать 1024 таких чисел и отнимется всего 10 битов энтропии. Неплохо.
Здравствуйте, vsb, Вы писали:
vsb>Для n = 3 и 8 битов получается 63.25, для 4 битов получается 50.4. Это я просто перебором сделал. В принципе формула очевидная — (256 — n) / (n + 1). Хм. Сам решил что-ли, методом подбора. Если так, то выходит, что от исходного числа битов "энтропии" отнимается примерно log2(n) битов (ну там +-1, лень думать).
