Псевдослучайное сжатие

Пост который я давно хотел написать,

и пишу чтобы не забыть...

Это было давно, как теперь кажется, я учился в университете и полдня мне рассказывали интересные штуки(кроме случаев когда рассказывали не очень).

И на предмете защита информации, или как-то подобно называвшемся, очень часто предметы имели длинные названия, которые все сокращали до очень кратких фраз, была у нас тема псевдослучайные последовательности на основе xor и регистров сдвига. Это очень простые по логике устройства умевшие генерировать n-1 чисел, где n это 2 в степени разрядности регистра сдвига. Почему на одно число меньше, если это очень хорошее число установить в регистре сдвига, то он будет всегда выдавать только его. Все остальные числа спокойно переходили одно в другое по случайному закону, но всегда по одной последовательности. Ну зато они и псевдослучайная последовательность. Разнообразие этих генераторов немного все таки ограничено, так некоторые варианты, как я помню можно упростить до более простых.

Ну так вот нужно было по части последовательности определить конфигурацию генератора. Для этого нужна половина максимального периода и провести какие-то сложные вычисления с использованием мнимой единицы. У меня что-то эти вычисления не сходились. Поэтому я решил пойти по другому пути придумать свой алгоритм. На бумаге он очень хорошо сходился и главное давал результат гораздо быстрее сложных математических расчетов.

Он заключался как я помню в том чтобы выписать эту всю последовательность в виде треугольника, так как в качестве результата всегда выдавалось полное содержимое регистра сдвига без изменений. То-есть в первой строке первый известное состояние когда известны все биты в регистре, в следующем со сдвигом на один разряд, неизвестен 1 бит. И так до конечного состояния. Теперь предполагая о предположительной длине этого регистра сдвига, в моем случае это было просто, я знал что длина исходных данных равна половине полной последовательности и мог четко предположить, что регистр сдвига будет определенной длины. Хотя это в общем-то особого значения так как этот алгоритм можно использовать и для неизвестной длины цепочки, только корректируя результирующую формулу. В этом случае - нужно выполнить полный перебор всех возможных значений формулы от минимального до максимально возможной разрядности. Что хорошо для медленной скорости передачи исходной последовательности, но для случае если скорость передачи сравнима со скоростью пересчета то смысла в этом алгоритме нет, он не дает той-же скорости как исходный классический метод с мнимыми числами.

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


Как я выше указал мы берем от совсем минимальной длины регистра сдвига до максимально возможной для данной последовательности - мы где-то можем примерно проверить разрядность до длины полученной последовательности-2. Причина в том что на полной последовательности мы ничего проверить не можем, на -1 мы можем хоть уже делать предположения, о том какие настройки возможны, на -2 можем начать отбрасывать точно не подходящие и прогнозировать множество возможных вариантов. Но так как мы начинаем с минимального - мы делаем предположение основываясь множестве уравнений полученных вычитанием верхней строки из строки расположенной на 1 строку ниже. Чем длиннее предполагаемая разрядность, тем меньше уравнений и больше множество вариантов. И начиная с минимальной разрядности мы отбрасываем варианты.

В моем случае для простых случаев в рамках 4 бита регистр, 8 бит полупоследовательность - это выполняется быстрее и по сложности проще. Но зато благодаря этому я нашел пару неточностей в решениях полученных другими (были возможны более короткие регистры) и главное сдал лабу.

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

P.S.: Я мог конечно что-то забыть и здесь есть неточности, но все же пока все не забыл, постарался максимально  правильно все описать.