Section 3.2.1.2 của "The art of computer programming" (part 2)

newbie_lap_trinh · March 12, 2019, 2:49pm

Mình không hiểu phần:
Therefore the period is length of m if and only if the period of the senquence with X0 = 0 is of length m

Và bổ đề R khi p = 2 ở phần:

These arguments show that it is necessary in general to have a = 1+q.p^f,where p^f>2 and q is not a multiple of p,whenever k= p^e

Mình có ba câu hỏi:

Tại sao khi dãy có length m tại X0 = 0 ta suy ra dãy có length m với X0 trong khoảng [1;m] ?
Tại sao phải xét riêng trường hợp p=2 trong khi có thể dùng cách tương tự như khi p>2 để chứng minh?
Nếu cần xét riêng thì tại sao a = 1 +qp^f ?

rogp10 · March 12, 2019, 4:46am

Do mod m và [1…m-1] chỉ có m-1 phần tử, không đủ nên phải có 0. Ta có dãy ~~vô hạn~~ tuần hoàn rồi thì bắt đầu chỗ nào cũng như nhau thôi, ý câu đó là vậy.

Thay p = 2 và với a = 4k+3, đồng dư thức trở thành a^(2^(e - 1) - 1)/(a - 1) = 0 (mod 2^e)

tức là tạch, chu kì tối đa 2^(e-1).

newbie_lap_trinh · March 12, 2019, 3:59am

Anh giải thích rõ hơn chỗ “dãy vô hạn rồi thì bắt đầu chỗ nào cũng như nhau thôi” được không ạ ?

rogp10 · March 12, 2019, 5:44am

Cụ thể là ntn: “Chạy một vòng sân” nghĩa là chạy trên chu vi (hay đường piste ) của sân về điểm xuất phát. Vậy bắt đầu chỗ nào không quan trọng, đủ một vòng thôi Không mất tính tổng quát, chọn x0 = 0.

Hệ thức x[n+1] = (a*x[n] + c) mod m ứng với sơ đồ Horner sau:

  | X0 c  c  c  ...
-------------------
a | X0 X1 X2 X3 ...

tức là đa thức g(y) = X0*y^n + c*(y^(n-1) + y^(n-2) + ... + 1)
hay x[n] = g(a) mod m.

Khử X0 bằng cách gán cho nó là zero. Số hạng còn lại là lũy thừa mod nhân với hằng số nên phải có chu kì.

rogp10 · December 29, 2021, 5:00pm

Với p = 2 thì a = 4k - 1\ (k \in Z^+) \Rightarrow a^2 - 1 = 16k^2 - 8k \equiv 0 \pmod 8 nên không áp dụng được Lemma P.

Như vậy 2^{e+1} \mid a^{2^{e-1}} - 1 (dùng HĐTĐN để quy nạp ) , mà a - 1 = 4k - 1 - 1 = 2(2k-1) nên (a^{2^{e-1}} - 1) \div (a-1) \equiv 0 \pmod {2^e}

Như vậy xét riêng p = 2 là vì (\pm 1)^2 = 1.