Trong khi đang đọc Khóa học mật mã toán học của Baumslag và cộng sự, tôi không hiểu các phần chứng minh của Định lý 2.3.3, cụ thể là điều kiện cần :
Để cho $n\in\mathbb{N}$ với $n=2^m,m\geq1$ và để cho $a,b\in\mathbb{Z}$ như vậy mà $f:\mathbb{Z}_n\to\mathbb{Z}_n, x\to\overline{a}x+\overline{b}$ là một bộ tạo đồng dư tuyến tính. Hơn nữa hãy để $s\in\{0,1,\dots,n-1\}$ được cho và $x_0=\overline{s},x_1=f(x_0),\dots.$ Sau đó trình tự $x_0,x_1,\dots$ là định kỳ với độ dài thời gian tối đa $n=2^m$ nếu những điều sau đây giữ:
- $a$ là số lẻ.
- Nếu $m\geq2$ sau đó $a\equiv1\mod{4}.$
- $b$ là số lẻ và $\overline{b}\neq\overline{0}.$
Bằng chứng đi như sau cho $m\geq2$ và như vậy $n\geq 4$:
Giả sử (1), (2) và (3) được thỏa mãn. Chúng tôi cho thấy rằng chúng tôi có được khoảng thời gian dài tối đa $n = 2^m$ vì $x_0=\overline{0}$ chứng minh định lý.
Để cho $x_0=\overline{0}.$ Chúng tôi có được đệ quy $$x_k = (\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})\overline{b}$$ vì $k\geq1.$ Từ $b$ là lẻ chúng ta có
$$x_k=\overline{0}\iff(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=\overline{0}.$$
Chúng tôi viết $k = 2^rt$ với $r\geq0$ và $t$ số lẻ. sau đó
$$\overline{0}=(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=(\overline{1}+\overline{a}+\ dấu chấm+\overline{a}^{2^r-1})(\overline{1}+\overline{a}^{2^r}+(\overline{a}^{2^r})^2+ \dots+(\overline{a}^{2^r})^{t-1}).$$
Thừa số thứ hai đồng dư với 1 modulo 2 và do đó
$$2^m|(1+a+\dots+a^{k-1})\iff2^m|(1+a+\dots+a^{2^r-1}).$$
số nguyên $1+a+\dots+a^{2^r-1}$ chia hết cho $2^r$ vì nó là tổng của $2^r$ các số lẻ nhưng không chia hết cho $2^{r+1}.$ Nó sau đó $r\geq m\iff2^m|k.$ Vì vậy $x_k=\overline{0}$ xảy ra cho $k\geq1$ lần đầu tiên khi $k=n=2^m$.
Tôi không viết nghiêng phần cuối cùng (từ "The integer..."). Tôi sẽ rất vui nếu ai đó có thể khai sáng cho tôi.
