Регистрация Войти
Рейтинг:0
neolith avatar Crypto

Может ли алгоритм Берлекампа-Месси ложно обнаружить LFSR?

флаг cn
neolith

Возможно ли, что BMA обнаруживает неприводимый полином из последовательности, которая не была сгенерирована LFSR? Я загружаю последовательность в BMA, предполагая, что она была сгенерирована LFSR. Он обнаруживает полином определенной длины, но последовательность не может быть восстановлена ​​из этого полинома. Я не хочу предполагать, что в реализации BMA есть ошибка. Если на вопрос выше нельзя ответить «да» в любом случае, реализация должна быть неправильной.

52
1 + 0
Рейтинг:4
kodlu avatar Crypto
флаг sa
kodlu

Нет.

Дана произвольно длинная последовательность $(x_1,\ldots,x_t,\ldots)$ рассмотрим его начальные сегменты.

Любая (конечная) последовательность $$x^{(n)}:=(x_1,\ldots,x_n)$$может быть сгенерирован циркулирующим LFSR той же длины. Просто переключайте биты, без нажатий.

BMA обнаружит это, если не существует более короткого LFSR, который генерирует $х^{(п)}$. И будет сходиться, чтобы правильно определить кратчайший LFSR, который однозначно генерирует $х^{(п)}$ если вы подадите ему в два раза больше начальных битов $х^{(2n)}.$

Исправьте свой код.

0 + 1
neolith avatar
флаг cn
neolith
Спасибо. По крайней мере, теперь мне не нужно работать над предположениями
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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