Перемешиватель данных (shuffler)

Обычно для решения этой задачи используют некий ГСПЧ для получения пар индексов кодов в блоке данных, которые меняют местами. Неприятность этого метода в том, что трудно гарантировать, что какая-то часть данных не останется на том же месте. Также не совсем понятно, сколько же перестановок нужно сделать, чтобы достичь приемлемого результата, хотя для надёжности можно просто пройтись по всем кодам сообщения и обменять каждый со случайным. Но есть ещё одна неприятность - если генератор имеет плохое распределение по квадрату (а линейный конгруэнтный именно такой болезнью и болеет, и причём безнадёжно), то при определённых размерах блока можно нарваться на зацикливание выдаваемых значений. Я довольно долго шёл к идее быстрого псевдослучайного перемешивателя данных (shuffler) и считаю, что она заслуживает вашего внимания не только как алгоритм для скремблирования.

Немного теории. В пункте 3.2.1.2 книги Д.Кнута «Искусство программирования» можно найти критерии для выбора множителя для линейного конгруэнтного генератора, чтобы длина генерируемой последовательности равнялась модулю. Что это означает? Это значит, что для генератора с модулем m каждое значение от 0 до m-1 будет выдано ровно один раз. Зачем это нам? Вспомним, что для нашего перетасовщика было бы желательно гарантировать, что все байты(коды) сообщения поменяли своё место. То есть, если длина данного блока данных равна этому самому m, то нам будет достаточно просто записывать очередной входной байт(код) сообщения в выходной буффер по индексу, равному очередному значению из генератора. Простота этого алгоритма настолько сооблазнительна, что я не мог пройти мимо.

Но, как всегда случается с чем-то сооблазнительным, не обошлось без проблем. Во-первых, не все m одинаково хороши. Из той же главы той же книги мы видим, что если m является произведением простых чисел в первой степени, то полного перебора элементов мы достичь не можем в принципе (не считая перебора подряд, что нам, конечно, не интересно). Получается, что получить нужный нам генератор с заданной длиной последовательности нельзя, и, следовательно, если у нас сообщения произвольной длины, то мы не всегда можем найти такой генератор. Тупик? А действительно ли нам нужны генераторы произвольной длины? Вспомним о том, что для потенциального взломщика знание длины сообщения очень даже небесполезно. Тогда мы уже знаем и способ борьбы, который мы успешно применяли для генератора, зависящего от входных данных. Правильно, надо подбросить случайный мусор, и лучше всего перед полезными данными. Правда, есть проблема в том, что в каждом блоке нужно как-то указывать количество полезной информации в нём. Если же в вашем случае длина всех сообщений/блоков данных фиксирована, то вы вы можете зафиксировать и m - выбрать первое удобное для вас значение, которое больше длины входного блока и удовлетворяет критерию из теоремы A из 3.2.1.3 из книги.

Теперь о самом критерии для параметров генератора xn+1=(a*xn+c) mod m:

1. c и m взаимно просты;

2. a - 1 кратно p для всех простых делителей p числа m;

. a - 1 должно быть кратно 4, если m кратно 4.

Как бы этого достичь малой кровью? Я предлагаю такой вариант:

= 2n, где n>3;

с = p, p - простое число & p>2;

a = 4*k+1.

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

Прочтите также:

Электронные генераторы мультивибратор. Назначение, принцип действия, применение
Мультивибратор представляет собой релаксационный генератор колебаний почти прямоугольной формы. Он является двухкаскадным усилителем на резисторах с положительной обратной ...

Модели полупроводниковых диодов
Цель работы: Изучить основные физические модели p-n переходов, находящихся в равновесном состоянии и при электрическом смещении, а так же модели ВАХ диодов, соответствующие различным про ...

Фильтр верхних частот Баттерворта
До недавнего времени результаты сопоставления цифровых и аналоговых устройств в радиоаппаратуре и технических средствах электросвязи не могли не вызывать чувства неудовлетворённости. Циф ...

Основные разделы

Copyright © 2008 - 2019 www.techmatch.ru