În timp ce citesc Un curs de Criptografie Matematică de Baumslag et al., am dificultăți în înțelegerea unor părți ale demonstrației teoremei 2.3.3, și anume condiția necesară:
Lăsa $n\în\mathbb{N}$ cu $n=2^m,m\geq1$ si lasa $a,b\in\mathbb{Z}$ astfel încât $f:\mathbb{Z}_n\la\mathbb{Z}_n, x\la\overline{a}x+\overline{b}$ este un generator de congruență liniară. Mai departe lasa $s\în\{0,1,\dots,n-1\}$ fi dat și $x_0=\overline{s},x_1=f(x_0),\dots.$ Apoi secvența $x_0,x_1,\dots$ este periodică cu lungimea maximă a perioadei $n=2^m$ dacă sunt valabile următoarele:
- $a$ este ciudat.
- Dacă $m\geq2$ atunci $a\equiv1\mod{4}.$
- $b$ este ciudat și $\overline{b}\neq\overline{0}.$
Dovada merge după cum urmează pt $m\geq2$ și, astfel $n\geq 4$:
Presupunem că (1), (2) și (3) sunt satisfăcute. Arătăm că obținem lungimea maximă a perioadei $n = 2^m$ pentru $x_0=\overline{0}$ care demonstrează teorema.
Lăsa $x_0=\overline{0}.$ Obținem recursiv $$x_k = (\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})\overline{b}$$ pentru $k\geq1.$ De cand $b$ este ciudat ca avem
$$x_k=\overline{0}\iff(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=\overline{0}.$$
Noi scriem $k = 2^rt$ cu $r\geq0$ și $t$ ciudat. Atunci
$$\overline{0}=(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=(\overline{1}+\overline{a}+\ puncte+\overline{a}^{2^r-1})(\overline{1}+\overline{a}^{2^r}+(\overline{a}^{2^r})^2+ \dots+(\overline{a}^{2^r})^{t-1}).$$
Al doilea factor este congruent cu 1 modulo 2 și, prin urmare
$$2^m|(1+a+\dots+a^{k-1})\iff2^m|(1+a+\dots+a^{2^r-1}).$$
Numărul întreg $1+a+\dots+a^{2^r-1}$ este divizibil cu $2^r$ întrucât este o sumă de $2^r$ numere impare dar nedivizibile cu $2^{r+1}.$ Rezultă că $r\geq m\iff2^m|k.$ Prin urmare $x_k=\overline{0}$ apare pentru $k\geq1$ pentru prima dată când $k=n=2^m$.
Nu urmăresc ultima parte în cursiv (din „The integer...”). M-as bucura daca cineva m-ar putea lumina.
