Во время чтения Курс математической криптографии Баумслаг и др., у меня возникли проблемы с пониманием части доказательства теоремы 2.3.3, а именно необходимого условия:
Позволять $n\in\mathbb{N}$ с $n=2^m,m\geq1$ и разреши $а,б\в\mathbb{Z}$ такой, что $f:\mathbb{Z}_n\to\mathbb{Z}_n, x\to\overline{a}x+\overline{b}$ является генератором линейных сравнений. Далее пусть $s\in\{0,1,\dots,n-1\}$ быть дано и $x_0=\overline{s},x_1=f(x_0),\dots.$ Затем последовательность $x_0,x_1,\точки$ является периодическим с максимальной длиной периода $n=2^m$ если выполняется следующее:
- $а$ странно.
- Если $m\geq2$ тогда $а\эквив1\мод{4}.$
- $b$ странно и $\overline{b}\neq\overline{0}.$
Доказательство выглядит следующим образом для $m\geq2$ и поэтому $n\geq 4$:
Предположим, что (1), (2) и (3) выполнены. Покажем, что мы получаем максимальную длину периода $n = 2^m$ за $x_0=\overline{0}$ что доказывает теорему.
Позволять $x_0=\overline{0}.$ Получаем рекурсивно $$x_k = (\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})\overline{b}$$ за $k\geq1.$ С $b$ странно у нас
$$x_k=\overline{0}\iff(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=\overline{0}.$$
Мы пишем $к = 2^rt$ с $r\geq0$ и $t$ странный. затем
$$\overline{0}=(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=(\overline{1}+\overline{a}+\ точки+\overline{a}^{2^r-1})(\overline{1}+\overline{a}^{2^r}+(\overline{a}^{2^r})^2+ \dots+(\overline{a}^{2^r})^{t-1}).$$
Второй множитель конгруэнтен 1 по модулю 2 и, следовательно,
$$2^m|(1+a+\dots+a^{k-1})\iff2^m|(1+a+\dots+a^{2^r-1}).$$
Целое число $1+а+\точки+а^{2^r-1}$ делится на $2^r$ так как это сумма $2^r$ нечетные числа, но не делятся на $2^{г+1}.$ Следует, что $r\geq m\iff2^m|k.$ Следовательно $x_k=\overline{0}$ происходит для $k\geq1$ в первый раз когда $k=n=2^m$.
Я не следую самой последней части, выделенной курсивом (из «Целое число...»). Буду рад, если кто-то сможет меня просветить.
