№task-number1task-section.task-number.Привести следующие два элемента последовательности, сформированной линейным конгруэнтным методом, если предыдущие 3 элемента последовательности такие: 348, 65, 139, а все вычисления выполняются в поле $\mathbb{F}_{499}$.
Решение:
1pt 0pt 0pt
используя предыдущие значения выхода генератора, строим систему уравнений:
$$\left\{ {\begin{array}{*{20}c}
348 \cdot a + c = 65 \mod 499 \\
65 \cdot a + c = 139 \mod 499 \\
\end{array} } \right. ;$$
из системы уравнений находим $a = 467$ и $c = 223$;
используя найденные значения, находим следующие элементы последовательности:
1pt 0pt 0pt
$x_{3} = a x_{2} + c \mod m = 467 \cdot 139 + 223 \mod 499 = 266$;
$x_{4} = a x_{3} + c \mod m = 467 \cdot 266 + 223 \mod 499 = 194$.
Ответ: 266, 194.
№task-number1task-section.task-number.Приведите предыдущие 5 бит выхода генератора псевдослучайной последовательности, основанного на регистре сдвига с линейной обратной связью, если известно, что характеристический полином регистра – $m\left(x\right)=x^{5} + x^{3} + 1$ (см. рис.), а дальнейшая последовательность такова: $1, 1, 0, 1, 0, 1$.
Это формула бита, который на следующей итерации станет битом $b_1$, то есть значение функции обратной связи регистра.
$b_5 = b_0\oplus b_{3}$ – формула выходного бита, если известны остальные биты и значение функции обратной связи;
За счёт последних 5 бит выхода восстанавливаем состояние регистра $\overrightarrow{s_{1}}=\left(b_{1}, b_{2}, b_{3}, b_{4}, b_{5}\right) = \left(1, 0, 1, 0, 1\right)$. Далее начинаем отматывать время назад.
Ответ (в порядке выдачи бит генератором): $0, 1, 1, 0, 1$.
Краткое оформление второй части задачи можно увидеть в таблице[table:task-lfsr-1-short-solution]. Таблица заполняется снизу вверх (так как нам нужны предыдущие биты, а не следующие). Последняя строка таблицы соответствует последнему известному состоянию регистра – последним 5 битам последовательности. Столбцы таблицы связаны формулой $b_{5} \oplus b_{3} = b_0 $. Ответ находится в первых 5 элементах первого столбца.
$b_{5}$
$b_{4}$
$b_{3}$
$b_{2}$
$b_{1}$
$b_0$
$\overrightarrow {s_{-5}}$
0
0
1
1
0
1
1
$\overrightarrow {s_{-4}}$
1
1
1
0
1
1
1
$\overrightarrow {s_{-3}}$
1
1
0
1
1
1
0
$\overrightarrow {s_{-2}}$
0
0
1
1
1
0
1
$\overrightarrow {s_{-1}}$
1
1
1
1
0
1
0
$\overrightarrow {s_{0}}$
1
1
1
0
1
0
1
$\overrightarrow {s_{1}}$
1
1
0
1
0
1
$\cdot$
Таблица 17.1 — Краткое оформление решения задачи №task-section.task-number в виде таблицы
Ответ:$0, 1, 1, 0, 1$.
№task-number1task-section.task-number.Укажите характеристический полином и приведите следующие 5 бит выхода генератора псевдослучайной последовательности, основанного на регистре сдвига с линейной обратной связью, если известно, что степень характеристического полинома регистра – $m\left(x\right)$ – равна 5, а предыдущая последовательность такова: $0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1$. Порядок бит в последовательности соответствует порядку их генерации РСЛОС.
Решение.Каждый бит выходной последовательности есть функция 5 предыдущих выходных бит вида $b_0 = f\left( b_{5} \dots b_1 \right) $. В данных обозначениях $b_{5}$ является наиболее ранним битом, а $b_1$ – последним, который сгенерировал РСЛОС непосредственно перед генерацией бита $b_0$. Вид функции задаётся характеристическим многочленом, который и нужно найти.
Итого ответ на вторую часть задачи: $0, 1, 1, 0, 1$.
Краткое оформление второй части задачи можно увидеть в таблице[table:task-lfsr-2-short-solution]. Таблица заполняется сверху вниз. Столбцы таблицы связаны формулой $b_{5} \oplus b_{4} \oplus b_{3} \oplus b_{2} = b_0 $. В первой строке записаны первые 5 бит полученной последовательности. Выполняя последовательно операции над регистром, мы получим все следующие биты. Начать заполнение таблицы можно со строчки $\overrightarrow s_{6}$ (то есть с последних 5 бит, данных в условии задачи), строки выше приведены для возможности (само)контроля студента. Ответом являются последние 5 бит в первом столбце.
$b_{5}$
$b_{4}$
$b_{3}$
$b_{2}$
$b_{1}$
$b_0$
$\overrightarrow {s_{0}}$
0
0
1
0
0
1
1
$\overrightarrow {s_{1}}$
1
1
0
0
1
1
0
$\overrightarrow {s_{2}}$
0
0
0
1
1
0
0
$\overrightarrow {s_{3}}$
0
0
1
1
0
0
0
$\overrightarrow {s_{4}}$
1
1
1
0
0
0
0
$\overrightarrow {s_{5}}$
1
1
0
0
0
0
1
$\overrightarrow {s_{6}}$
0
0
0
0
0
1
0
$\overrightarrow {s_{7}}$
0
0
0
0
1
0
1
$\overrightarrow {s_{8}}$
0
0
0
1
0
1
1
$\overrightarrow {s_{9}}$
0
0
1
0
1
1
0
$\overrightarrow {s_{10}}$
1
1
0
1
1
0
1
$\overrightarrow {s_{11}}$
0
0
1
1
0
1
0
$\overrightarrow {s_{12}}$
1
1
1
0
1
0
1
$\overrightarrow {s_{13}}$
1
1
0
1
0
1
0
$\overrightarrow {s_{14}}$
0
0
1
0
1
0
0
$\overrightarrow {s_{15}}$
1
1
0
1
0
0
0
Таблица 17.2 — Краткое оформление решения второй части задачи №task-section.task-number в виде таблицы