Luận văn Dãy ngẫu nhiên, giả ngẫu nhiên và ứng dụng

1 − ∑ 𝑃(𝐿) 𝑇−1 𝐿=𝑀 Các xác suất trên sẽ rất nhỏ nếu L khá gần M. Thành thử để áp dụng được tiêu chuẩn χ2 cần phải có một xâu có kích thước (độ dài) rất lớn, thường là hàng ngàn giá trị. II.2.6. Kiểm tra hoán vị Chia dãy thành n nhóm, mỗi nhóm gồm t phần tử (Yj, Yj+1, , Yj+t-1) với (0≤j≤n-1). Có thể giả thiết rằng các phần tử trong các nhóm đó là khác nhau. Sau đó, tính số lần gặp một nhóm nào đó trong số t! nhóm có thể. Đương nhiên, xác suất để có thể gặp mỗi nhóm là 1 𝑡! . Trên cơ sở các giá trị tính được ta sử dụng tiêu chuẩn χ2 . Tuy nhiên, cần thấy rằng với dãy có tập giá trị M lớn thì Thang Long University Libraty 24 dù độ dài của nhóm t là nhỏ thì cỡ mẫu (độ dài của xâu) cần có để kiểm tra sẽ phải rất lớn vào khoảng 5.C 𝑡 𝑀 .t! phần tử. Ví dụ: với M = 4, t = 3 thì dãy 100 phần tử sau đây: 021| 321| 031| 203|130|210|231|201|320|130|213|021|302|130|120|132| 102|321|023|103|120|123|023|120|210|320|123|023|120|213|012|320|132 Cũng chỉ đảm bảo mỗi kiểu trong số 𝐶4 3. 3! kiểu có được không nhiều hơn 4 nhóm, tức là không đủ để sử dụng tiêu chuẩn χ2. II.2.7. Tiêu chuẩn về nhóm (Runtest) Cho một xâu gồm 2 giá trị X và Y được sắp xếp theo một trật tự bất kì: X X Y Y Y X Y Y X X Y Y Y X X X Khi đó, người ta gọi một nhóm của xâu là một loạt các phần tử cùng loại đứng kề nhau. Như vậy nếu xâu gồm n phần tử thì số nhóm ít nhất có thể là 2 và nhiều nhất là n ( mỗi nhóm gồm chỉ một phần tử). Ví dụ với xâu gồm 16 phần tử như trên có cả thảy 4 nhóm X ( hai nhóm 2 phần tử, 1 nhóm ba phần tử và 1 nhóm một phần tử) và 3 nhóm Y (2 nhóm ba phần tử và 1 nhóm hai phần tử). Định lý: Nếu X, Y được xắp một cách ngẫu nhiên thì số nhóm U của một xâu gồm n phần tử của dãy, trong đó có n1 giá trị của X, n2 giá trị của Y (n1+ n2 = n) là một đại lượng ngẫu nhiên với phân phối xác suất P(U = m) = [ 2Cn1−1 ( 1 2m−1). Cn2−1 ( 1 2m−1) Cn n1 ; Nếu m chẵn (m = 2k) Cn1−1 ( 1 2m−3). Cn2−1 ( 1 2m−1) + Cn1−1 ( 1 2m−1). Cn2−1 ( 1 2m−3) Nếu m lẻ (m = 2k + 1) Bây giờ với một dẫy ngẫu nhiên bất kỳ, để kiểm tra tính ngẫu nhiên của dãy, trước hết ta chia giá trị của dãy thành hai loại X và Y,. Một số được gọi là X nếu nó nhỏ hơn trung vị (med) của dãy, các số còn lại được gọi là Y rồi sắp 25 xếp lại chúng theo trật tự vốn có ta được dãy mới gồm chỉ hai loại phần tử X và Y như trên. Quy tắc nhóm có miền bác bỏ giả thiết H0 về tính ngẫu nhiên của dãy xác định bởi công thức: (U ≤ U∝ 2⁄ ) ∪ (U ≥ U (1− ∝ 2) ) Với α là mức ý nghĩa của tiêu chuẩn và 𝑈∝ 2⁄ = max{𝑈: 𝑃(𝑈 ≤ 𝑈′) ≤ ∝ 2⁄ } (∗) 𝑈1−∝ 2⁄ = min{𝑈: 𝑃 (𝑈 ≤ 𝑈′) ≥ 1 − ∝ 2⁄ } (∝< 0,5) (*): Theo bảng các giá trị tới hạn của quy tắc nhóm Nếu giả thiết H0 là đúng và n1 →∞, n2 →∞, sao cho 𝑛1 𝑛 → 𝛾0 ≠ 0 thì 𝑈−2𝛾𝛿𝑛 2𝛾𝛿√𝑛 (𝛾 = 𝑛1 𝑛 , 𝛿 = 𝑛2 𝑛 ) có phân phối tiệm cận chuẩn N(0,1). Ví dụ 1: Có một dãy nhị phân gồm n = 12 giá trị được sắp xếp như sau: 101101010000 Hãy kiểm tra về tính ngẫu nhiên của dãy với α = 0,05 Giải: Số nhóm của dãy U=8. Theo bảng X ta có: U0,025 = 3; U0,975 = 10 tức là miền bác bỏ giá trị H0; (U≤3)∪ (U≥10) với U = 8 giả thiết H0 được chấp nhận. Ví dụ 2: Cho một dãy số thực: 0,3; 0,4; 0,2; 0,7; 0,9; 0,4; 0,6; 0,3; 0,1; 0,6; 0,7; 0,4; 0,0; 0,2; 0,3; 0,9; 0,4; 0,3; 0,7; 0,6. Hãy kiểm tra giả thiết H0 về tính ngẫu nhiên của dãy trên với mức ý nghĩa α = 0,05 Thang Long University Libraty 26 Giải: Trước hết trung vị của dãy trên sẽ là 0,45 và do vậy dãy có thể viết lại như sau: XXXYYXYXXYYXXXXYXXYY Số nhóm của dãy U = 10. Theo bảng X ta có U0,025 = 2; U0,975 = 9 Vậy miền bác bỏ của tiêu chuẩn là (U≤6) ∪ (U≥15), n1 = số phần tử x = 12, n2 = số phần tử y = 8, n1 > n2. Từ đó ta thấy giả thiết H0 bị bác bỏ. II.2.8. Tiêu chuẩn nghịch thế Cho dãy X1, X2, X3, Xn. Khi đó ta gọi số nghịch thế của số đứng vị trí thứ j (số các số đứng sau mà nhỏ hơn số trước), Xj là số các số đứng sau nó Xi với i > j mà Xi < Xj; (1≤I, j≤N). Ví dụ trong dãy số (3, 5, 1, 4, 2, 7) thì số nghịch thế của số thứ nhất X1 = 3 là 2 vì có hai số (1 và 2) đứng sau mà nhỏ hơn 3. Tương tự, số nghịch thế của 5 là 3, của 1 là 0, của 4 là 1, của 2 là 0 và của 7 là 0. Ký hiệu số nghịch thế của phần tử Xj là Ij (j = 1, 2, 3, , N) và I = ∑ Ij n−1 j=1 Người ta chứng minh được rằng: P(I = m) = Pn(m) N ; 0 ≤ m ≤ N(N − 1) 2 Trong đó PN(m) là số hoán vị chứa đúng m nghịch thế của N phần tử, đồng thời với N khá lớn đại lượng Z = I−E(I) √Var(I) có phân phối chuẩn N(0,1), trong đó: E(I) = N(N − 1) 4 , Var(I) = 2N3 + 3N2 − 5N 72 Với những kết quả trên tiêu chuẩn nghịch thế để kiểm tra giả thiết H0 về tính ngẫu nhiên của dãy sẽ có miền bác bỏ với mức ý nghĩa α: 27 ¦W = {I < I N; (1− ∝ 2) } ∪ {I > I N; ( ∝ 2) } Các giá trị I N; (1− ∝ 2 ) và I < I N; ( ∝ 2 ) được trình bày trong bảng sau: N α 0,99 0,975 0,95 0,05 0,025 0,01 10 9 11 13 31 33 35 12 16 18 21 44 47 49 14 24 27 30 60 64 66 16 34 38 41 78 81 85 18 45 50 54 98 102 107 20 59 64 69 120 125 130 30 152 162 171 263 272 282 40 290 305 319 460 474 489 50 473 495 514 710 729 751 60 702 731 756 1013 1038 1067 70 977 1014 1045 1369 1400 1437 80 1299 1344 1382 1777 1815 1860 90 1668 1721 1766 2238 2283 2336 100 2083 2145 2198 2751 2804 2866 (Bảng các giá trị tới hạn của quy tắc nghịch thế) Ví dụ: Cho mẫu gồm 20 số liệu quan sát lấy từ một xâu của dãy ngẫu nhiên như sau: 5,5; 5,1; 5,7; 5,2; 4,8; 5,7; 5,0; 6,5; 5,4; 5,8; 6,8; 6,6; 4,9; 5,4; 5,9; 5,4 6,8; 5,8; 6,9; 5,5 Kiểm tra tính ngẫu nhiên của dãy với mức ý nghĩa α = 0,05. Ta thấy nghịch thế với phần tử thứ nhất (5,5): I1 = 8 tương tự I2 = 3, I3 = 8, I4 = 3, I18 = 1, I19 = 1, I20 = 0. Thang Long University Libraty 28 Vậy I = ∑ Ii = 62 20 i=1 Với N=20, theo bảng trên ta có: I(20;0,975) = 64; I20:0,025 = 125 Do I = 62 < I20:0,975 nên giả thiết về tính ngẫu nhiên của dãy bị bác bỏ. Trên đây là một số tiêu chuẩn thống kê cơ bản để kiểm tra tính ngẫu nhiên của dãy. Như đã nhấn mạnh trước đây, các tiêu chuẩn thống kê không quan tâm tới đặc trưng toán học hoặc vật lý của các dãy được sinh ra. Trong thực tế các dãy thường được sinh ra bởi các nguyên lý kỹ thuật hoặc các thuật toán trên cơ sở các lý thuyết chặt chẽ về tính giả ngẫu nhiên của dãy-đặc biệt tính phân phối đều của các phần tử của dãy thường được khảo sát một cách kỹ lưỡng ngay từ chính thuật toán sinh. Điều đó đôi khi lại làm mất đi tính ngẫu nhiên của dãy và do vậy các dãy đó cũng cần phải loại bỏ bằng các tiêu chuẩn thống kê. Thành thử khác với các bài toán kiểm định thống kê thông thường - Các tiêu chuẩn 2 áp dụng cho dãy ngẫu nhiên cần phải có miền bác bỏ bao gồm cả những giá trị V tính được đủ nhỏ, tức là 𝑃{𝑉 < 𝑋1−∝ 2 } = 1−∝. Cũng cần phải nói thêm rằng không thể có được một phép so sánh đầy đủ về sự “mạnh, yếu” của các tiêu chuẩn đã đưa ra ở trên. Thực tế thấy rằng có những dãy thỏa mãn tiêu chuẩn này nhưng lại không thể vượt qua được các tiêu chuẩn có vẻ “đơn giản” hơn, hoặc thậm chí cùng một tiêu chuẩn sử dụng cho cùng một dãy với các xâu có độ dài khác nhau nhưng lồng nhau (xâu ngắn chứa trong xâu dài hơn) thì kết quả cũng hoàn toàn khác nhau. Điều đó cũng lý giải cho việc cần phải có một bộ khá đa dạng các tiêu chuẩn kiểm tra. Ngoài ra có lẽ một trong những nguyên nhân cơ bản của việc cần thiết phải kiểm tra bằng nhiều tiêu chuẩn là ở chỗ người tạo chuỗi cần phải chứng minh cho người sử dụng chuỗi của mình là ngẫu nhiên. Đương nhiên người sử dụng cũng cần phải tin rằng mình đang sử dụng chuỗi ngẫu nhiên. Nếu một người nào đó sử dụng chính dãy của mình thì cũng cần phải có đủ cơ sở cả lý thuyết lẫn thực nghiệm để tin tưởng vào sản phẩm của mình. 29 CHƯƠNG III CÁC DÃY GIẢ NGẪU NHIÊN Khái niệm về dãy giả ngẫu nhiên Trong nhiều ứng dụng cả trong các lĩnh vực thực tế lẫn trong kỹ thuật, đặc biệt là kỹ thuật tính toán, người ta luôn cần đến các dãy số ngẫu nhiên. Chẳng hạn các dãy số ngẫu nhiên được sử dụng trong các phép chọn mẫu ngẫu nhiên trong thống kê hoặc dùng làm các giá trị xuất phát để thực hiện các chương trình tính toán phức tạp. Đặc biệt trong bảo vệ thông tin nói chung và trong mật mã nói riêng thì chỉ số ngẫu nhiên của các dãy số ngẫu nhiên hoặc thậm chí của số được sinh ra tức thì một cách ngẫu nhiên đóng vai trò quan trọng trong việc bảo đảm an toàn cho một bộ mật mã. Trong kỹ thuật nguồn lý tưởng cho các số ngẫu nhiên là kết quả đo các đại lượng vật lý ngẫu nhiên, chẳng hạn như nhiễu nhiệt hoặc nhiễu điện mà trước kia để làm được điều đó người ta phải tạo ra các thiết bị chuyên dụng, thì ngày nay với kỹ thuật tính toán và máy tính điện tử, việc tạo ra một dãy số ngẫu nhiên được thực hiện một cách tự động, có khi chỉ bằng một lệnh máy tính đơn giản, hoặc bằng một bộ sinh số ngẫu nhiên mà cốt lõi của nó là một thuật toán sinh số ngẫu nhiên đơn giản. Thực tế thì những số, hay các dãy số như vậy không phải là ngẫu nhiên hoàn toàn bởi lẽ dù sao thì nó cũng được sinh ra từ các quy tắc tất định, có mối liên hệ với nhau ( tương quan ) được xác định bởi chính các công thức toán học có trong thuật toán. Các số như vậy chỉ có vẻ là ngẫu nhiên, “trông” giống như hay có nhiều thuộc tính của dãy ngẫu nhiên. Ngoài ra cũng phải nói thêm rằng nhiều khi chính những dãy số ngẫu nhiên thực sự lại không đáp ứng những yêu cầu của ứng dụng – ví dụ nó không Thang Long University Libraty 30 thể đồng bộ, hoặc khôi phục lại để tái sử dụng với một mục đích nào đó ( bởi vì nó là ngẫu nhiên ). Vậy thì giải pháp trong các tình huống như vậy ( mà thường xảy ra trong thực tế ) là hãy tạo ra các dãy số có nhiều thuộc tính giống với các thuộc tính của một dãy ngẫu nhiên, và thỏa mãn các yêu cầu của thực tế ứng dụng. Các dãy ngẫu nhiên như vậy được gọi là các dãy giả ngẫu nhiên (tựa ngẫu nhiên). Định nghĩa một cách hình thức về dãy số giả ngẫu nhiên như sau: Định nghĩa 1: Dãy giả ngẫu nhiên (tựa ngẫu nhiên) là các dãy số được sinh ra từ các qui tắc tất định mà có các tính chất cơ bản gần giống với các tính chất của một dãy số ngẫu nhiên, đó là: 1- Mỗi số được tạo ra phải có phân phối xác suất gần như nhau; 2- Nếu có hai số Rk và Rt nào đó “hơi khác nhau” thì với mọi i = 1, 2, hai số rk+i và rt+i phải khác nhau rõ rệt, tức là giữa các số của dãy phải có mối tương quan yếu. Cũng không có một định nghĩa toán học chặt chẽ và chung cho dãy giả ngẫu nhiên, bởi lẽ nó phụ thuộc vào chính các phương pháp, ( thuật toán ) sinh ra nó và loại số được sinh ra ( Ví dụ: số nhị phân, số thập phân,). Với các số giả ngẫu nhiên được sinh ra bởi các thuật toán thì các thuộc tính cơ bản về tính ngẫu nhiên cần quan tâm của dãy lại là: 1- Tính phụ thuộc yếu giữa phần tử aj bất kỳ với các phần tử khác của dãy – hay tính tương quan yếu giữa các phần tử. 2- Độ dài của chu kỳ của dãy, tức là các giá trị của dãy sẽ lặp lại sau ít nhất N phần tử ( dãy có chu kỳ T). Còn yêu cầu về tính phân phối xác suất đều giữa các phần tử của dãy được xác định bởi chính độ dài của dãy. Dưới đây chúng ta xem xét một vài dãy giả ngẫu nhiên thường gặp với tính chất ngẫu nhiên tốt của chúng. 31 Dãy giả ngẫu nhiên thặng dư bậc hai III.2.1. Định nghĩa Gọi N = {N = P.Q, với P, Q nguyên tố cùng độ dài và P ≡ Q ≡ 3 mod 4}. Giả sử N  N, gọi XN = { x2 mod N | x  ZN* } là tập thặng dư bậc hai của mod N. Đặt X = NN XN – gọi là miền hạt giống. Xác định các ánh xạ T: X  X, với T(x) = x2 mod N, với x  XN. B: X  {0,1}, với B(x) = 0, nếu x – chẵn, và B(x) = 1, nếu x – lẻ. Khi đó bộ ba được gọi là bộ tạo dãy giả ngẫu nhiên x2 mod N. Cụ thể, cho N N, x0 x  XN, thì bộ tạo x2 mod N sẽ tạo ra dãy bít như sau: - Thông qua ánh xạ T sẽ tạo ra dãy {xn}n: xi+1 = xi 2 mod N, i = 0, 1, 2, - Thông qua ánh xạ B sẽ tạo dãy {bn}: bi = B(xi), i = 0, 1 ,2, Ví dụ: 1.Cho p = 3, q = 7. Khi đó có: Z21* = { 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. # Z21*= (21) = 12. X21 = {1, 4, 16} = { x 2 mod 21 | x  Z21*}. # Z21 = (21)/4 = 3. Thang Long University Libraty 32 2.Cho N = 7.19 = 133, x0 = 4. Khi đó có: {xn} = 4, 16, 123, 100, 25, 93, {bn} = 0, 0, 1, 0, 1, 1, Chu kỳ của {bn} là bằng 6, tức bằng λ(λ(N)). (λ: hàm Carmichael). III.2.2. Giả thuyết thặng dư bậc hai Giả sử N là tích hai số nguyên tố lẻ. Khi đó nếu gọi ZN*(+1) = { x  ZN*: ( 𝑥 𝑁 ) = +1 (Jiacôbi )}, ZN*(-1) = { x  ZN*: ( 𝑥 𝑁 ) = -1 (Jiacôbi )}, |ZN*(+1)| = | ZN*(-1)| = (N)/2. Ngoài ra: XN = { x  ZN*(+1): x= a 2 mod N}, và | XN| = (N)/4. *Bài toán thặng dư bậc hai: Cho N và x  ZN*(+1), hãy quyết định xem x  XN hay x  ZN*(+1)\ XN. *Giả thuyết thặng dư bậc hai (Quadratic Residuacity Assumption – QRA): Giả thuyết này cho rằng bất kỳ một thủ tục hiệu quả nào dùng đoán nhận thặng dư bậc hai sẽ không chính xác đối với một bộ phận nào đó của các dữ kiện đầu vào. Giả sử poly(.) là một đa thức. Giả sử P[N, x] là thủ tục thời gian đa thức (xác suất) với đầu vào là N, x có độ dài n, đầu ra là 0 hoặc 1 ( tức là P[N, x] = 0 hoặc 1). Giả sử  là hằng số cố định, 0 <  < 1. Giả sử t là một số nguyên dương. 33 Khi đó với n đủ lớn và với toàn bộ hay  phần của các số nguyên N độ dài n, N là tích của hai số nguyên tố lẻ, xác suất để P[N, x] đoán sai thặng dư bậc hai P[N, x] = { 0 𝑛ế𝑢 x  𝑋𝑁 1 𝑛ế𝑢 x 𝑋𝑁 , Với x chọn tùy ý đều trong ZN*(+1), và với một dãy tung đồng xu cho trước (trong trường hợp thủ tục xác suất ), luôn vượt quá giá trị 1/nt, tức là: ( ∑ 𝑷𝒓𝒐𝒃(𝑷[𝑵, 𝒙] − đ𝒐á𝒏 𝒔𝒂𝒊)𝑥𝑍𝑁∗ (+1) (𝑁)/2 ) > 1 𝑛𝑡 Chú ý: Với N = p.q, với p, q là các số nguyên tố lẻ. Khi đó với mỗi a = x2  XN sẽ có 4 căn bậc hai là ∓x, (N∓ x) mod N. Tuy nhiên nếu lấy p ≡ q ≡ 3 mod 4, thi căn bậc hai của a là duy nhất, tức là ánh xạ: aXN  a2 mod N  XN là 1 -1, tức là một hoán vị trên tập XN. III.2.3. Tính chất của bộ tạo x2 mod N Tính chất 1: Tồn tại một thuật toán tất định hiệu quả A khi cho trước N và phân tích thừa số nguyên tố của nó, và với bất kỳ thặng dư bậc hai, x0 ZN*,sẽ tính toán một cách hiệu quả dư bậc hai duy nhất x-1 mod N, sao cho (x- 1) 2 mod N = x0, tức là: A(p, q, x0) = x-1. Tính chất 2: Định nghĩa a. Một bộ dự đoán P(.,.) là một thủ tục thời gian đa thức xác suất với đầu vào N, b1, , bk; bi  {0, 1} và k ≤ poly(|N|), đầu ra là 0 hoặc 1. b. P gọi là ε – trội đối với N trong việc dự đoán về phía trái dãy tạo bởi x2 mod N, nếu và chỉ nếu với k nào đó, k ≤ poly(|N|), ta có: Thang Long University Libraty 34 ( ∑ 𝑷𝒓𝒐𝒃[𝑷(𝑵,𝒃𝟏(𝒙),,𝒃𝒌(𝒙))= 𝒃𝟎(𝒙)]𝑥𝑋𝑁 (𝑁)/4 ) > 1 2 + 𝜀, ở đây bi(x) = Parity (x2 mod N). Định lí Dưới giả thuyết thặng dư bậc hai QRA, bộ tạo x2 mod N là bộ tạo dãy giả ngẫu nhiên mạnh không thể dự đoán được về phía trái. Định lí Dưới giả thuyết thặng dư bậc hai QRA, dãy tạo bởi bộ x2 mod N qua được mọi test thống kê thời gian đa thức xác suất. (Tức là mọi phép test thống kê thời gian đa thức xác suất nhằm phân biệt dãy này với dãy tung đồng xu ngẫu nhiên là vô hiệu quả). Tính chất Định nghĩa: Giả sử M = 2𝑒 . 𝑝1 𝑒1 . 𝑝2 𝑒2 𝑝𝑘 𝑒𝑘. Hàm Carmichael – λ định nghĩa trên tập các số nguyên dương M như sau: 𝜆(2𝑒) = { 2𝑒−1, 𝑛ế𝑢 𝑒 = 1, 𝑒 = 2, 2𝑒−2, 𝑛ế𝑢 𝑒 > 2 λ(M) = LCM[𝜆(2𝑒), (𝑝1 − 1)𝑝1 𝑒1−1, , (𝑝𝑘 − 1)𝑝𝑘 𝑒𝑘−1 ]. Chú ý: λ(M) ≡ 1 mod M, nếu (, M) = 1. Định lí: Kí hiệu (x0) và b(x0) lần lượt là chu kì của dãy {xi} và {bi}. Khi đó ta có (x0) | λ(λ(N)), b(x0) | (x0) | λ(λ(N)). Phương pháp toàn đẳng tuyến tính III.3.1. Công thức 35 Đa số các bộ sinh số ngẫu nhiên được biết đến hiện nay chỉ là các trường hợp riêng hoặc biến dạng của một phương pháp đã được nhà toán học H.Lechmen đề xuất từ những năm 1948 như sau: Trước hết chọn 4 số khởi đầu: + X0 : giá trị gốc X0  0 + a : hệ số nhân a  0 + c : gia số c  0 + m : modyl m  X0, a, c Khi đó dãy ngẫu nhiên cần tìm sẽ nhận được từ tương ứng sau: Xn+1 = (aXn + c) mod m, n  0 (1) Dãy nhận được theo công thức trên được gọi là dãy toàn đẳng tuyến tính. Ví dụ: Với X0 = a = c = 7; m = 10, dãy số của chúng ta sẽ là 7,6,9,0,7,6,9,0, Rõ ràng dãy của chúng ta không có vẻ gì là ngẫu nhiên như mong muốn. Vậy thì dãy sinh ra là ngẫu nhiên hay chí ít là giả ngẫu nhiên các số liệu khởi đầu phải tuân theo những nguyên tắc nào đó. Ví dụ trên cũng cho thấy dãy sinh ra bởi (1) chắc chắn có chu kì, tức là cuối cùng thì các số trong dãy sẽ lập nên một chu trình mà chu trình đó sẽ được lặp đi lặp lại vô hạn lần. Chu trình lặp được gọi là chu kỳ và độ dài của chu kỳ là điều chúng ta quan tâm. Với dãy đưa ra ở trên thì độ dài chu kỳ là 4. Một dãy thực tế được đưa ra sử dụng đương nhiên cần có chu kỳ lớn dù mục đích có khác nhau. Để đơn giản cách viết sau này, người ta đưa vào tham số b = a – 1 và bây giờ (1) có thể được tổng quát bởi Xn+k = (a kXn + (a k – 1) 𝑐 𝑏 ) mod m (k  0; n  0) Công thức trên biểu diễn phần tử thứ (n+k) qua phần tử thứ n. Thang Long University Libraty 36 Dãy tương ứng với các phần tử theo k lập nên một dãy mới với các hệ số nhân ak và gia số (ak – 1) 𝑐 𝑏 . a) Lựa chọn Modyl (m). Ở đây chúng ta sẽ xem xét việc cần phải chọn số m như thế nào. Đương nhiên số m cần phải đủ lớn, bởi lẽ chu kỳ của dãy toàn đẳng tuyến tính không thể lớn hơn m. Thông thường người ta chọn m=𝜔±1. Trong đó 𝜔 là kích thước một từ của máy tính (số nguyên lớn nhất chứa được trong một từ của máy). Khi đó chu kỳ lớn nhất của dãy có thể đạt được không nhỏ hơn 109. b) Lựa chọ hệ số nhân a. Chu kỳ cực đại chỉ là một trong những dấu hiệu cần thiết cho tính ngẫu nhiên của dãy bởi lẽ một dãy ngẫu nhiên tuyệt đối (về mặt chu ky) có thể coi như một dãy có chu kỳ rất lớn, nhưng một dãy có chu kỳ cực đại thì lại chưa chắc là ngẫu nhiên. Ví dụ: Xn+1=(Xn+1) mod m có chu kỳ bằng đúng m nhưng lại không là ngẫu nhiên. Ví dụ trên cũng cho thấy hoàn toàn có thể chọn được a, c để chu kỳ đạt được tối đa bằng m. Định lý sau đây cho chúng ta các phương pháp lựa chọn a, c sao cho chu kỳ đật cực đại m. Định lý : Độ dài chu kỳ toàn đẳng tuyến tính bằng m khi và chỉ khi: (i1) c và m nguyên tố cùng nhau (i2) b=a-1 là bội số của mọi số nguyên tố p là ước của m (i3) b là bội số của 4 nếu m là bội của 4 Chứng minh: Ý tưởng của việc chứng minh định lý đã hình thành từ rất lâu. Ngay từ năm 1961 M Guin beager chứng minh với trường hợp riêng m=2e. Sau đó một năm hai nhà toán học Khal và Đôbel đã chứng minh cho trường hợp tổng quát. 37 Việc chứng minh định lý cần đến một vài kiến thức bổ trợ về lý thuyết số. Bạn đọc nếu không quan tâm đến khía cạnh lý thuyết của vấn đề có thể bỏ qua phần này. Tuy nhiên, các kết quả lý thuyết số dưới đây cũng có những ý nghĩa riêng. Bổ đề 1:Giả sử P là số nguyên tố, còn e là số nguyên dương sao cho Pe>2. Nếu 𝑥 ≡ 1(𝑚𝑜𝑑 𝑝𝑒); 𝑥 ≠ (𝑚𝑜𝑑 𝑝𝑒+1) (1) Thì 𝑥𝑝 ≡ 1(𝑚𝑜𝑑 𝑝𝑒+1); 𝑥𝑝 ≠ 1(𝑚𝑜𝑑 𝑝𝑒+2) (2) Chứng minh: Chúng ta có x=1+𝑞𝑝𝑒, trong đó q là một số nguyên nào đó mà không phải bội của p. Theo công thức khai triển Newton ta có: 𝑥𝑝 = 1 + 𝐶𝑝 1𝑞𝑝𝑒 +⋯+ 𝐶𝑝 𝑝−1𝑞𝑝−1𝑝(𝑝−1)𝑒 + 𝑞𝑝𝑝𝑝𝑒 = 1+q𝑝𝑒+1 (1 + 1 𝑝 𝐶𝑝 2𝑞𝑝𝑒 + 1 𝑝 𝐶𝑝 3𝑞2𝑝2𝑒 +⋯+ 1 𝑝 𝐶𝑝 𝑝𝑞𝑝−1𝑝(𝑝−1)𝑒) Biểu thức trong dấu ( ) là những số nguyên, ngoài ra mỗi số hạng (trừ số hạng đầu tiên) là bội số của p vì dẽ dàng thấy rằng 𝐶𝑝 𝑘 (1 < 𝑘 < 𝑝) chia hết cho p. Do vậy 1 𝑝 𝐶𝑝 𝑘𝑝(𝑘−1)𝑒 chia hết cho p bởi vì (k-1)e>1 với (pe>2). Như vậy xp=1+q’𝑝𝑒+1 với q’ là số nguyên không chia hết cho p, và do vậy bổ đề được chứng minh. Bổ đề 2: Giả sử số m được khai triển thành các thừa số nguyên tố m=𝑝1 𝑒1 𝑝𝑡 𝑒𝑡. Khi đó độ dài 𝜆 chu kỳ của dãy toàn đẳng tuyến tính xác định bởi các tham số (X0,a,c,m) bằng bội số chung nhỏ nhất của độ dài 𝜆𝑖 của các chu kỳ của các dãy toàn đẳng tuyến tính (𝑋0 𝑚𝑜𝑑 𝑃𝑗 𝑒𝑗 , 𝑎 𝑚𝑜𝑑 𝑃 𝑗 𝑒𝑗 , 𝐶 𝑚𝑜𝑑 𝑃 𝑗 𝑒𝑗 , 𝑃𝑗 𝑒𝑗 ) (1 ≤ 𝑗 ≤ 𝑡) Thang Long University Libraty 38 Chứng minh: Bằng cách quy nạp theo t, chúng ta chỉ cần chứng minh rằng, nếu r và s là hai số nguyên tố cùng nhau thì độ dài chu kỳ 𝝀 của dãy toàn đẳng tuyến tính xác định bởi điều kiện ban đầu (X0,a,e,r,s) sẽ bằng bội số chung nhỏ nhất của độ dài 𝜆1, 𝜆2 của chu kỳ của các dãy toàn đẳng tuyến tính (𝑋0 𝑚𝑜𝑑 𝑟, 𝑎 𝑚𝑜𝑑 𝑟, 𝑐 𝑚𝑜𝑑 𝑟, 𝑟) và (𝑋0 𝑚𝑜𝑑 𝑠, 𝑎 𝑚𝑜𝑑 𝑠, 𝑐 𝑚𝑜𝑑 𝑠, 𝑠) Chúng ta thấy rằng nếu ký hiệu các dãy trên lần lượt là 𝑋𝑛, 𝑌𝑛, 𝑍𝑛 thì rõ ràng 𝑌𝑛 = 𝑋𝑛 𝑚𝑜𝑑 𝑟 và 𝑍𝑛 = 𝑋𝑛 𝑚𝑜𝑑 𝑠 với mọi n ≥ 0 Ngoài ra 𝑋𝑛 = 𝑋𝑘 khi và chỉ khi 𝑌𝑛 = 𝑌𝑘 và 𝑍𝑛 = 𝑍𝑘 Bây giờ, giả sử 𝝀’ là bội số chung nhỏ nhất của các độ dài 𝜆1, 𝜆2. Ta sẽ chứng minh rằng 𝝀’= 𝝀. Bởi vì 𝑋𝑛 = 𝑋𝑛+𝜆 với mọi số đủ lớn ta có 𝑌𝑛 = 𝑌𝑛+𝜆 (do đó 𝝀 phải là bội số của 𝜆1) và 𝑍𝑛 = 𝑍𝑛+𝜆 (đó 𝝀 phải là bội số của 𝜆2). Và vì vậy 𝝀 ≥ 𝝀’. Mặt khác chúng ta thấy rằng 𝑌𝑛 = 𝑌𝑛+𝜆′ và 𝑍𝑛 = 𝑍𝑛+𝜆′ với n đủ lớn và do vậy 𝑋𝑛 = 𝑋𝑛+𝜆′ tức là ta lại có 𝝀 ≤ 𝝀’ thành thử 𝝀 =𝝀’. Bổ đề chứng minh xong. Bây giờ ta chuẩn bị chứng minh định lý. Chú ý rằng bổ đề nêu trên đã đủ để chứng minh định lý khi m là lũy thừa của một số nguyên tố. Thật vậy, bất phương trình: 𝑃1 𝑒1 𝑃𝑡 𝑒𝑡 = 𝝀 = Bội số chung nhỏ nhất của (𝝀1, 𝝀2, , 𝝀𝑡) ≤ 𝝀1. 𝝀2𝝀𝑡 ≤ 𝑃1 𝑒1 . 𝑃2 𝑒2 𝑃𝑡 𝑒𝑡 Xẩy ra khi và chỉ khi 𝝀𝑗 = 𝑃𝑗 𝑒𝑗 với mọi 1 ≤ j ≤ t Vì vậy, chúng ta giả sử rằng m=pe trong đó p là số nguyên tố, còn e là số nguyên dương. Rõ ràng với a=1, định lý đúng. Vì vậy có thể giả thiết rằng a>1. Độ dài chu kỳ bằng m khi và chỉ khi mỗi số nguyên x ( 0 ≤ x ≤ m) gặp trong dãy chỉ một lần. Như vậy chu kỳ sẽ có độ dài bằng m khi và chỉ khi độ dài của 39 chu kỳ với dãy có 𝑋0 = 0 cũng bằng m. Do vậy, ta có quyền giả thuyết rằng 𝑋0 = 0 và khi đó ta có: 𝑋𝑛 = ( 𝑎𝑛−1 𝑎−1 )c mod m (b = a-1) (*) Nếu c và m không nguyên tố cùng nhau thì 𝑋𝑛 không bao giờ có thể bằng 1. Vì vậy điều kiện thứ nhất của định lý là rõ ràng. Ngoài ra với giả thiết X0=0 thì số n nhỏ nhất để 𝑋𝑛 = 𝑋0 = 0 chỉ có thể là n=m. Vì vậy từ chú ý (*) và điều kiện 1 đã nói ở trên việc chứng minh định lý của ta chỉ còn lại là chứng minh bổ đề sau: Bổ đề 3: Giả sử rằng 1<a<pe , trong đó p là số nguyên tố. Nếu 𝝀 là số dương nhỏ nhất sao cho (𝑎λ − 1) 𝑎 − 1 ⁄ ≡ 0 (𝑚𝑜𝑑 𝑝𝑒) thì 𝝀=𝑝𝑒 khi và chỉ khi { 𝑎 ≡ 1 𝑚𝑜𝑑 𝑝 với p > 2 𝑎 ≡ 1 𝑚𝑜𝑑 4 với p = 2 Chứng minh: Giả sử rằng 𝝀=𝑝𝑒. Nếu a≠1 (mod p) thì (𝑎𝑛−1) 𝑎−1 ≡ 0 (𝑚𝑜𝑑 𝑝𝑒) trong và chỉ trong trường hợp khi an -1 ≡ 0 ( 𝑚𝑜𝑑 𝑝𝑒). Diều kiện 𝑎𝑝 𝑒 -1 ≡ 0 ( 𝑚𝑜𝑑 𝑝𝑒) khi đó dẫn đến 𝑎𝑝 𝑒 ≡ 1 ( 𝑚𝑜𝑑 𝑝) nhưng từ đó lại dẫn đến 𝑎𝑝 𝑒 ≡ 𝑎 ( 𝑚𝑜𝑑 𝑝). Điều đó không đúng (𝑝𝑒 > 1). Nếu P=2 và a≡ 3(𝑚𝑜𝑑4) thì (𝑎2 𝑒−1 − 1) 𝑎 − 1 ⁄ ≡ 0 (𝑚𝑜𝑑 2𝑒). Và do vậy a sẽ có dạng a=1+𝑝𝑓.q với 𝑝𝑓 > 2, còn q không là bội của p với 𝝀= 𝑝𝑒 bất kỳ. Còn lại chỉ cần phải chỉ ra điều kiện đủ để 𝝀= 𝑝𝑒. Sử dụng bổ đề 1, ta có: 𝑎𝑝 𝑔 ≡ 1 (𝑚𝑜𝑑 𝑝𝑓+𝑔), 𝑎𝑝 𝑔 ≠ 1 (mod 𝑝𝑓+𝑔+1) Và vì vậy (𝑎𝑝 𝑔 − 1)/(𝑎 − 1) ≡ 0 (𝑚𝑜𝑑 𝑝𝑔) (𝑎𝑝 𝑔 − 1)/(𝑎 − 1) ≢ 0 (𝑚𝑜𝑑 𝑝𝑔+1) } (**) Thang Long University Libraty 40 Đặc biệt (𝑎𝑝 𝑒 − 1)/(𝑎 − 1) ≡ 0 (𝑚𝑜𝑑 𝑝𝑒). Như vậy, dãy toàn đẳng tuyến tính với điều kiện ban đầu (0,a,1,pe) có Xn= (𝑎n − 1) (𝑎 − 1)⁄ 𝑚𝑜𝑑 𝑝 𝑒 và vì vậy có chu kỳ 𝝀 tức là Xn=0 khi và chỉ khi n là bội số của 𝝀. Nhưng điều này lại chỉ có thể được thực hiện với 𝝀=pg , cùng với (**) ta có 𝝀=pe , tức là định lý được chứng minh. III.3.2. Tiêu chuẩn tần số Định lý : Giả sử rằng các tham số ban đầu (X, a, c, m) được chọn sao cho dãy toàn đẳng tuyến tính sinh ra có chu kỳ cực đại. Ngoài ra, giả sử b=a-1, còn d là ước số chung lớn nhất của m và b. - Khi đó, xác xuất để Xn+1 < Xn bằng 1 2 + 𝑟 - Trong đó r = (2(c mod d) – d)/2m - Do đó: |𝑟| < 𝑑 2𝑚⁄ Đặt S(x) = (ax + c) mod m, khi đó X=S(Xn) và để chứng minh định lý ta chỉ cần tính các số nguyên x sao cho 0≤ 𝑥 ≤ 𝑚 và S(x)<x. Chúng ta cần chỉ ra rằng số đó phải bằng 1 2 (𝑚 + 2(𝑐 𝑚𝑜𝑑 𝑑) − 𝑑) Rõ ràng với a = 1 định lý đúng vì khi đó S(x) < x  x + c ≥ m tức là điều đó xảy ra đúng c lần. Bây giờ nếu ký hiệu ⌊𝛼⌋ Là số nguyên lớn nhất nhỏ hơn hoặc bằng 𝛼 , và c là số nguyên nhỏ nhất lớn hơn hoặc bằng 𝛼. Khi đó thì ⌊𝛼⌋ ≤ 𝛼 ≤ ⌈𝛼⌉. Khi đó với x là một số nguyên bất kỳ 0≤ 𝑥 < 𝑚 ta gọi k(x)=⌊(ã + 𝑐)/𝑚⌋, khi đó S(x) = ax + c - k(x).m và k(x) ≤ (ax+c)/m. Từ đó, ta có: (k(x).m - c)/a ≤ x < (k(x).m – c)/b (*) 41  𝑎𝑥+𝑐 𝑚 ≤ 𝑘(𝑥) ≤ 𝑏𝑥+𝑐 𝑚 < 𝑎𝑥+𝑐 𝑚 + 1 (**) Tức là k(x) xác định duy nhất, từ đó ta có: (i1) ⌈(𝑘𝑚 − 𝑐)/𝑎⌉ ≤ 𝑥 < ⌈(𝑘𝑚 − 𝑐)/𝑏⌉ , 0 < 𝑘 < 𝑎 do (*) (i2) ⌈𝑚 − 𝑐/𝑎⌉ ≤ 𝑥 < 𝑚 , (do 0≤x≤m và tính chất của k(x)) Khi đó số các số nguyên x sẽ bằng 𝑚 + ∑ ⌈(𝑘𝑚 − 𝑐)/𝑏⌉ − 0<𝑘≤𝑏 ∑ ⌈(𝑘𝑚 − 𝑐)/𝑎⌉ 0<𝑘≤𝑎 (***) Bây giờ định lý sẽ được chứng minh nếu ta chỉ ra được (***) bằng: [ 1 2 (𝑚 + 2(𝑐𝑚𝑜𝑑𝑑) − 𝑑)] Để làm điều đó trước hết ta đưa vào hàm 𝜎(𝑥) = ⌊𝑍⌋ + 1 − ⌈𝑍⌉ = { 1 0 𝑁ế𝑢 𝑍 𝑛𝑔𝑢𝑦ê𝑛 𝑁ế𝑢 𝑋 𝑘ℎô𝑛𝑔 𝑛𝑔𝑢𝑦ê𝑛 ((𝑍)) = 𝑍 − ⌊𝑍⌋ + 1 2 𝜎(𝑧) − 1 2 = 𝑍 − ⌈𝑍⌉ + 1 2 − 1 2 𝜎(𝑧) (Hàm đặc trưng của Z) Thay ký hiệu trên vào (***) ta có: (∗∗∗) = 1 2 (𝑚 − 1 + ∑ 𝜎( 𝑘𝑚 − 𝑐 𝑎 ) 0<𝑘≤𝑎 − ∑ 𝜎( 𝑘𝑚 − 𝑐 𝑏 ) 0<𝑘≤𝑏 + ∑ (( 𝑘𝑚 − 𝑐 𝑎 )) 0<𝑘≤𝑎 − ∑ (( 𝑘𝑚 − 𝑐 𝑏 )) 0<𝑘≤𝑎 ) Bởi vì a và m là nguyên tố cùng nhau nên (km-c) mod a chỉ nhận giá trị 0,1,(a-1) và do k≤a nên ∑ 𝜎( 𝑘𝑚 − 𝑐 𝑎 ) = 1; 0≤𝑘≤𝑎 ∑ (( 𝑘𝑚 − 𝑐 𝑎 )) = 0 0≤𝑘≤𝑎 Thang Long University Libraty 42 Ngoài ra, nếu m và b nguyên tố cùng nhau còn c và b nguyên tố cùng nhau thì (km-c)/b không thể nguyên. Vì vậy, thành phần thứ hai trong tổng trên bằng 0, còn (( 𝑘𝑚 − 𝑐 𝑏 )) = (( 𝑘𝑚 − 𝑑 ⌊ 𝑐 𝑑⌋ − 𝑐 𝑚𝑜𝑑 𝑑 𝑏 )) = (( 𝑘𝑚/𝑑 − ⌊𝑐/𝑑⌋ 𝑏/𝑑 )) − 𝑐 𝑚𝑜𝑑 𝑑 𝑏 + 1 2 𝜎 ( 𝑘𝑚/𝑑 − ⌊𝑐/𝑑⌋ 𝑏/𝑑 ) Lại do 0≤(c mod d)/b<1/(b/d) và m/d, b/d nguyên tố cùng nhau nên ∑ (( 𝑘𝑚 − 𝑐 𝑏 )) = 1 2 0≤𝑘≤𝑏 𝑑 − 𝑐 𝑚𝑜𝑑 𝑑 Và định lý được chứng minh. Việc dẫn ra cách chứng minh định lý trên chỉ nhằm mục đích chỉ ra rằng để chứng minh các tính chất lý thuyết của các chuỗi ngẫu nhiên toàn đẳng tuyến tính nói riêng và các chuỗi ngẫu nhiên sinh bằng các phương pháp toán học nói chung là rất phức tạp, nhưng dù sao công việc cũng đã hoàn thành. Việc chứng minh định lý còn chỉ ra rằng việc chọn a và c bất kỳ sẽ dẫn đến biến cố Xn+1<Xn với tần số tương ứng, trừ trường hợp d khá lớn mà d lớn là điều không mong muốn với phương pháp toàn đẳng tuyến tính. III.3.3. Tiêu chuẩn tương quan Tiêu chuẩn sau đây đưa ra mối quan hệ giữa các tham số a, b với một đắc trưng quan trọng hơn của dãy ngẫu nhiên là hệ số tương quan của hai phần tử trong suốt cả chu kỳ. Biết rằng hệ số tương quan được định nghĩa bởi công thức: 𝐶 = (𝑚 ∑ 𝑥𝑆(𝑥) − 0≤𝑥<𝑚 ( ∑ 𝑥 0≤𝑥<𝑚 ) 2 ) (𝑚 ∑ 𝑥2 − ( ∑ 𝑥 0≤𝑥<𝑚 ) 2 0≤𝑥<𝑚 )⁄ 43 Giả sử x’ là một phần tử sao cho S(x’)=0. Khi đó: S(x) = 𝑚(( 𝑎𝑥 + 𝑐 𝑚 ) + 𝑚 2 ) Nếu x ≠ x’ Ký hiệu: 𝜎(ℎ, 𝑘, 𝑐) = 12∑(( 𝑗 𝑘 ) ( ℎ𝑗+𝑐 𝑘 )) được gọi là hàm tổng Dedekin Khi đó do: ∑ 𝑥 0≤𝑥<𝑚 = 𝑚(𝑚 − 1) 2 và ∑ 𝑥2 0≤𝑥<𝑚 = 𝑚(𝑚 − 1)(2𝑚 − 1) 𝜎 Nên 𝑚𝜎(𝑎,𝑚, 𝑐) − 𝑆 + 6(𝑚 − 𝑥 − 𝑐) 𝑚2 − 1 Với m khá lớn nên 𝐶 ≈ 𝜎(𝑎,𝑚, 𝑐) 𝑚⁄ với sai số tuyệt đối < 6 𝑚 . Với hàm tổng quát Dedekin ta có công thức sau: Bổ đề 1: ( Luật cương hổ của tổng Dedekin) Nếu 0 ≤ 𝑐 < ℎ, 0 ≤ 𝑐 < 𝑘 và h,k là hai số nguyên tố cùng nhau thì: 𝜎(ℎ, 𝑘, 𝑐) + 𝜎(𝑘, ℎ, 𝑐) = ℎ 𝑘 + 𝑘 ℎ + 1 ℎ.𝑘 + 𝜎𝑐2 𝑘.ℎ − 3 (Việc chứng minh bổ đề trên cần các kiến thức về hàm phức nên ở đây ta sẽ bỏ qua) Bổ đề 2: Nếu h, k nguyên tố cùng nhau và 0<c<k thì 𝜎(ℎ, 𝑘, 𝑐) = 𝜎(ℎ, 𝑘, 𝑐 𝑚𝑜𝑑 ℎ) + 6𝑟 𝑏 (𝑐 + 𝑐 𝑚𝑜𝑑 ℎ − 𝑘) + 𝑑 Trong đó 𝑟 = ⌊𝑐/𝑛⌋, 𝑑 = 0 với (c mod h) ≠ 0 và d=3 với (c mod h) = 0 Bổ đề 3: Với mọi a, m, c ta có Thang Long University Libraty 44 𝐶 ≈ 1 𝑎 (1 − 6 𝑐 𝑚 + 6( 𝑐 𝑚 ) 2 ) Xấp xỉ trên với sai số không vượt quá 𝑎 𝑚 Từ các kết quả trên ta có các định lý: Định lý: Hệ số tương quan của một dãy toàn đẳng tuyến tính bất kỳ với chu kỳ cực đại được xác định gần đúng bởi 𝐶 ≈ 1 𝑎 (1 − 6 𝑐 𝑚 + 6( 𝑐 𝑚 ) 2 ) Với sai số nhỏ hơn 𝑎+6 𝑚 Ngoài các tiêu chuẩn trên, người ta còn đề xuất thêm tiêu chuẩn Phổ. Tuy nhiên để áp dụng tiêu chuẩn này cần một khối lượng tính toán lớn cùng với những kiến thức toán học hỗ trợ tương đối phức tạp – vượt qua giới hạn của luận văn này. III.3.4. Công suất Một dãy toàn đẳng tuyến tính có chu kỳ cực đại được gọi là có công suất là S nếu S là số nguyên nhỏ nhất sao cho bs ≡0 (mod m). Các tính toán chỉ ra rằng các dãy có công suất ≤3 sẽ không là ngẫu nhiên bởi lẽ có quan hệ giữa các phần tử cách nhau 3 vị trí, thông thường chọn S=4. Để nâng cao chu kỳ và tính ngẫu nhiên của dãy, người ta còn đề xuất nhiều phương pháp, ví dụ: 𝑋𝑛+1 = (𝑋𝑛 + 𝑋𝑛−𝑘) mod m Trong đó k là số đủ lớn và các giá trị gốc sẽ là (𝑋0, 𝑋1, , 𝑋𝑘) được chọn tùy ý. 𝑋𝑛 = (𝑎1𝑋𝑛−1 +⋯+ 𝑎𝑘𝑋𝑛−𝑘)𝑚𝑜𝑑 𝑝 45 Trong đó p là số nguyên tố lớn nhất có thể chứa trong một từ máy. Còn các hệ số 𝑎1, 𝑎2, , 𝑎𝑘 được chọn sao cho: 𝑓(𝑥) = 𝑥𝑘 − 𝑎1𝑥 𝑘−1 −⋯− 𝑎𝑘 là đa thức nguyên thủy theo mod p. Tổ hợp hai hay nhiều dãy toàn đẳng tuyến tính có chu kỳ nguyên tố cùng nhau: 〈𝑋𝑛〉 và 〈𝑌𝑛〉 〈𝑍𝑛〉 = 〈𝑋𝑛〉 + 〈𝑌𝑛〉 III.3.5. Ví dụ a. Dùng phương pháp toàn đẳng tuyến tính để sinh một dãy ngẫu nhiên Với xm+1 = 5xm +3 mod 16; cho x1 = 1; x2 = 8; x3 = 11, Ta được dãy gồm 100 số dưới đây: 1; 8; 11; 10; 5; 12; 15; 14; 9; 0; 3; 2; 13; 4; 7; 6; 1; 8; 11; 10; 5; 12; 15; 14; 9; 0; 3; 2; 13; 4; 7; 6; 1; 8; 11; 10; 5; 12; 15; 14; 9; 0; 3; 2; 13; 4; 7; 6; 1; 8; 11; 10; 5; 12; 15; 14; 9; 0; 3; 2; 13; 4; 7; 6; 1; 8; 11; 10; 5; 12; 15; 14; 9; 0; 3; 2; 13; 4; 7; 6; 1; 8; 11; 10; 5; 12; 15; 14; 9; 0; 3; 2; 13; 4; 7; 6; 1; 8; 11; 10; 5; 12; 15; 14; 9; 0. b. Dùng tiêu chuẩn kiểm tra tính đều để kiểm tra dãy số trên. Yi ni Npi(𝑝𝑖 = 1 16 ) (ni – npi) (𝑛𝑖 − 𝑛𝑝𝑖) 2 𝑛𝑝𝑖 0 6 6,25 -0,25 0,01 1 7 6,25 0,75 0,09 2 6 6,25 -0,25 0,01 3 6 6,25 -0,25 0,01 4 6 6,25 -0,25 0,01 5 6 6,25 -0,25 0,01 6 6 6,25 -0,25 0,01 7 6 6,25 -0,25 0,01 Thang Long University Libraty 46 8 7 6,25 0,75 0,09 9 6 6,25 -0,25 0,01 10 7 6,25 0,75 0,09 11 7 6,25 0,75 0,09 12 6 6,25 -0,25 0,01 13 6 6,25 -0,25 0,01 14 6 6,25 -0,25 0,01 15 6 6,25 -0,25 0,01 100 V= 0,48 Với α =0,05, ν = k – 1 = 16 – 1 = 15 →  0,05 2 = 25,0;  0,95 2 = 7,25; V = 0,48 → V = 0,48  (7,25; 25,0) → dãy trên không là dãy ngẫu nhiên theo tiêu chuẩn 2 c. Dùng tiêu chuẩn kiểm tra Xeri (cặp) để kiểm tra tính ngẫu nhiên của dãy số trên (q, r) ni pi npi (ni – npi) (𝑛𝑖 − 𝑛𝑝𝑖) 2 𝑛𝑝𝑖 (1, 8) 7 1/8 6,25 0,75 0,09 (11, 10) 7 1/8 6,25 0,75 0,09 (5, 12) 6 1/8 6,25 -0,25 0,01 (15, 14) 6 1/8 6,25 -0,25 0,01 (9, 10) 6 1/8 6,25 -0,25 0,01 (3, 2) 6 1/8 6,25 -0,25 0,01 47 (13, 14) 6 1/8 6,25 -0,25 0,01 (7, 6) 6 1/8 6,25 -0,25 0,01 n = 50 0,24 Với α =0,05, ν = k – 1 = 8 – 1 = 7 →  0,05 2 = 14,1;  0,95 2 = 2,17; V = 0,24 → V = 0,24  (2,17; 14,1) → dãy trên không là dãy ngẫu nhiên theo tiêu chuẩn 2 Dãy ghi dịch – Dãy ghi dịch tuyến tính III.4.1. Thanh ghi dịch phản hồi tuyến tính bậc n Định nghĩa: Thanh ghi dịch phản hồi bậc n là một bộ gồm n ô nhớ A0,,An1 và một phản hồi 𝑓(𝑥0, 𝑥1, , 𝑥𝑥−1) hoạt động theo nguyên tắc sau: Giả sử tại thời điểm k nội dung của ô Ai là ai(k), i=𝑖 = 1, 𝑛 − 1̅̅ ̅̅ ̅̅ ̅̅ ̅̅ với ai(k) ∈ GF(2) thì tại thời điểm kề ngay sau đó (thứ K+1) nội dung của ô Ai sẽ là: { 𝑎𝑖(𝑘 + 1) = 𝑎𝑖+1(𝑘) 𝑎𝑛−1(𝑘 + 1) = 𝑓[(𝑎𝑛−1(𝑘), 𝑎𝑛−2(𝑘), , 𝑎0(𝑘))] Thang Long University Libraty 48 Điều đó có nghĩa là thời điểm thứ k+1, các nội dung của ô đứng sau được chuyển ngay sang ô đứng ngay trước đó, còn nội dung của ô cuối cùng khi đó sẽ nhận giá trị của hàm 𝑓𝑘 = 𝑓(𝑎0(𝑘), 𝑎1(𝑘), , 𝑎𝑛−1(𝑘)) Cũng vậy, hàm 𝑓𝑘 được gọi là hàm phản hồi. Nếu 𝑓 có dạng tuyến tính tức là phụ thuộc tuyến tính và các giá trị 𝑎𝑖(𝑘), (i=0,1,,n-1) thì thanh ghi dịch được gọi là thanh ghi dịch tuyến tính. III.4.2. Dãy ghi dịch, dãy ghi dịch tuyến tính Định nghĩa : Dãy {𝑎𝑘 = 𝑎0(𝑘)} k=0,1,2, (Các giá trị của ô A0 tại thời điểm thứ k) được gọi là dãy ghi dịch bậc n với hàm số phản hồi 𝑓. Tổng quát hơn ta còn có định nghĩa sau: Định nghĩa : Dãy {𝑎𝑘}, k=0,1,2, với ai ∈ GF(2) được gọi là dãy ghi dịch bậc n nếu tồn tại một hàm 𝑓:𝑓: [𝐺𝐹(2)]𝑛 → 𝐺𝐹(2) sao cho 𝑎𝑛+𝑘 = 𝑓(𝑎𝑛−1+𝑘 , 𝑎𝑛−2+𝑘 , , 𝑎𝑘) ∀ k = 0, 1, 2 𝑎𝑛−2(𝑘) 𝑎0(𝑘) 𝑎1(𝑘) 𝑎2(𝑘) 𝑎𝑛−1(𝑘) 𝐶 = 𝑓(𝑎0(𝑘), 𝑎1(𝑘), , 𝑎𝑛−1(𝑘)) a0(k+1) . . an-2(k+1) an-1(k+1) 𝑎1(𝑘 + 1) . A0 An-2 Thời điểm k+1 A1 Thời điểm k A 0 A 2 A n-2 A 1 A n-1 49 Dãy ghi dịch được gọi là tuyến tính (hay phi tuyến) nếu hàm f là tuyến tính (phi tuyến) Ví dụ: c = (1 1 1 0 1 0 0) Ta thấy dãy này có chu kỳ bằng 7, ngoài ra có thể kiểm trứng thấy rằng: 𝑎3+𝑘 = 𝑎2+𝑘 ⨁ 𝑎𝑘 ∀ k = 0, 1, 2 Tức là 𝑓(𝑎2+𝑘 , 𝑎1+𝑘 , 𝑎𝑘) = 𝑎2+𝑘 ⨁ 𝑎𝑘 ở đây ⨁ được định nghĩa theo bảng trên. Vậy {𝑎𝑘} là dãy ghi dịch tuyến tính bậc 3. a b a ⨁ b 0 1 1 0 0 0 1 1 0 1 0 1 III.4.3. Tính chất của dãy ghi dịch. - Mọi dãy ghi dịch tuyến tính đều có chu kỳ (vì nó thỏa mãn điều kiện của nguyên lý chu trình); - Dãy ghi dịch bậc n sẽ có chu kỳ P<2n-1 bởi lẽ với ai∈ GF(2) thì dãy sẽ có tất cả 2n khả năng khác nhau và chu kỳ sẽ lặp lại khi có một khả năng bị gặp lại: Và cũng do vậy ta có: - Nếu gọi (𝑎0, 𝑎1, , 𝑎𝑛), ai∈ GF(2) là một n-tupel của dãy thì khi đó với dãy ghi dịch bậc n mỗi n-typel chỉ xuất hiện nhiều nhất là một lần trong một chu kỳ. - Hàm tương tự qua bậc 𝜏 Thang Long University Libraty 50 Nếu {𝑎𝑘}, k=0,1 Gọi 𝐶(𝜏)= 1 𝑝 ∑𝑏𝑖𝑏𝑖+𝜏 trong đó 𝑏𝑖 = 1 − 2𝑎𝑖, 𝑏𝑖 ∈ 𝑍, P là chu kỳ của dãy. Khi đó +𝐶(𝜏) = 𝐴(𝜏)−𝐷(𝜏) 𝑃 với 𝐴(𝜏) là số các cặp trùng nhau, 𝐷(𝜏) là số các cặp khác nhau của hai pha {𝑎0, 𝑎1, , 𝑎𝑝−1} và {𝑎0+𝜏, 𝑎1+𝜏, , 𝑎𝑝−1+𝜏} Trong đó p là chu kỳ của dãy. Từ đó ta có { + 𝐶(𝜏) = 𝐶(𝜏 + 𝑘𝑝) ∀𝑘 ∈ 𝑁 +| 𝐶(𝜏)| ≤ 1 - Độ phức tạp tuyến tính của dãy ghi dịch và M-dãy Định nghĩa : Số bậc n nhỏ nhất của thanh ghi dịch sinh ra dãy {𝑎𝑘} được gọi là độ phức tạp tuyến tính của dãy. Thấy rằng dãy có chu kỳ P có độ phức tạp tuyến tính là P vì đa thức phản hồi tuyến tính khi đó là 1+Xp tạo ra dãy có chu kỳ P. Ngoài ra, độ phức tạp tuyến tính bằng chính bậc của dãy. Định nghĩa: Dãy ghi dịch tuyến tính bậc n được gọi là M-dãy nếu chu kỳ của dãy là cực đại tức là bằng đúng 2n-1 - Định nghĩa về tính ngẫu nhiên của dãy (Định nghĩa của BLOM) Xét một dãy {𝑎𝑖}, i ≥ 0, 𝑎𝑖𝜖 GF(2) với chu kỳ P. Khi đó dãy được gọi là ngẫu nhiên nếu nó thỏa mãn 3 tính chất sau. + Tính chất 1: (Tiên đề 1) (Về tính đều của tần số đơn) Số bít 0 và số bít 1 trong một chu kỳ của dãy khác nhau nhiều nhất là 1 đơn vị. + Tính chất 2: (Tiên đề 2 - Tính đều của các khoảng (GAP)) Trong một chu kỳ của dãy số, các GAP có độ dài k bằng 1 2𝑘 . Ngoài ra, trong mỗi GAP độ dài k thì số GAP(0) bằng số GAP(1). Ví dụ: (1 0 0 0 0 0 1), (0 1 1 1 1 1 0): GAP(0) và GAP(1) cùng độ dài 5. 51 + Tính chất 3: (Tiên đề về tính tương quan) 𝐶(𝜏) = { 1 1 𝜏 = 𝑘𝑝 𝑞 𝜏 ≠ 𝑘𝑝 k ∈ Z, p: chu kỳ của dãy Trong đó đương nhiên |𝑞| < 1 III.4.4. Tính chất của các M-dãy Giả sử {𝑎𝑘} là một dãy nhị phân sinh ra bởi thanh ghi dịch có độ dài n (bậc n). khi đó: Định lý 1: M-dãy thỏa mãn tiên đề 1 – về tính đều. Thật vậy, do {𝑎𝑘} có chu kỳ 2 n -1 tức là các thanh ghi dịch sinh ra nó phải trải qua đúng 2n -1 trạng thái (trừ trạng thái 0 0 0). Mỗi trạng thái coi như biểu diễn nhị phân của 1 số nguyên dạng 𝑎𝑖 ∗ = 𝑏0 𝑖𝑥𝑛−1 + 𝑏1 𝑖𝑥𝑛−1 +⋯+ 𝑏𝑛−1 𝑖 với 𝑏𝑗 ∈ 𝐺𝐹(2), 𝑥 ∈ 𝐺𝐹(2), j=0,1,..,n-1 Trong đó: 𝑏𝑛−1 𝑖 = 𝑎𝑖; 𝑖 = 0,1,2, , 2 𝑛−1 Rõ ràng 𝑎𝑖 = { 0 ai ∗ chẵn 1 ai ∗ lẻ Do tập các số nguyên {1,2, 2𝑛−1} có 2𝑛−1 số lẻ và 2𝑛−1 − 1 số chẵn nên tiên đề 1 thỏa mãn. Định lý 2: M-dãy thỏa mãn tiên đề 2 (Tính đều của GAP) Trước hết chú ý rằng với M-dãy bậc n, trong một chu kỳ của dãy mỗi n- typel chỉ xuất hiện đúng một lần (trừ ra n-tupel toàn 0). Do vậy, GAP toàn 0, hay toàn 1 chỉ tồn tại trong một chu kỳ của dãy khi độ dài k của GAP thỏa mãn: k≤ n + Với k=n đương nhiên chỉ có một n-tupel toàn số 1; + Với k=n-1 chỉ và chỉ có một GAP(n-1) số 0 dạng (1 0 00 1). Và một GAP(n-1) số 1 dạng (0 1 11 0) Thang Long University Libraty 52 + Với 1 ≤ 𝑘 ≤ 2. Giả sử ta có một n-tupel có dạng (0 11⏟ 𝑘 𝑎𝑖𝑘 𝑎𝑛⏟ 𝑛−𝑘−2 Vậy đương nhiên do n-k-2 số sau là tùy ý nên sẽ có 2n-k-2 số loại như vậy. Điều đó cũng đúng với loạt độ dài k cùng kiểu nhưng bao gồm k số 0. Từ đó, ta có tổng số loạt trong một chu kỳ sẽ là: 𝐿 = 2(∑2𝑛−𝑘−2 𝑛−2 𝑘=1 ) + 2 = 2𝑛−1 = 𝑃 + 1 2 Trong đó P là chu kỳ của dãy. Định lý 3: M-dãy thỏa mãn tiên đề 3 (tiên đề về tính không tương quan). Thật vậy, gọi {𝐴𝑖(𝑖 = 1, 𝑝)} là một dãy có độ dài P nhị phân nào đó với P là chu kỳ của dãy ghi dịch, trong đó: 𝐴1 = {𝑎1, 𝑎2, , 𝑎𝑝} 𝐴2 = {𝑎2, 𝑎3, , 𝑎𝑝,𝑎1} . 𝐴𝑃 = {𝑎𝑝, 𝑎1, , 𝑎𝑝−1,} 𝐴1 = {0,0, ,0} Có thể chứng minh rằng 𝐺 = {𝐴0, 𝐴1, , 𝐴𝑝} là một nhóm với phép cộng Bool. Từ đó, nếu ta đặt 𝐺∗ = {𝐵𝑖; 𝑖 = 0,1,2, . . , 𝑝} với 𝐵𝑖 = {𝑏𝑖 , 𝑏𝑖+1, , 𝑏𝑖−1} trong đó 𝑏𝑖 = 1 − 2𝑎𝑖 , 𝑏𝑖 ∈ 𝑍 Khi đó (𝐺∗⨂) với ⨂ là phép toán nhân số nguyên theo từng cặp vị trí tương ứng, cũng là một nhóm Abel. Ngoài ra: 𝐵𝑖⨂𝐵𝑗 = 𝐵𝑘 ≠ 𝐵0 do 𝐴𝑖⨂𝐴𝑗 = 𝐴𝑘 ≠ 𝐴0 với i ≠ j 53 𝐵𝑖⨂𝐵𝑖 = 𝐵0 = {−1,−1, , −1} Do 𝐵𝑖⨂𝐵𝑗 = 𝐵𝑘 nên {𝐵𝑘 = 𝑏𝑖𝑏𝑖+𝑟; 𝑏𝑖+1𝑏𝑖+𝑟+1; ; 𝑏𝑖−1+𝑟𝑏𝑖−1} trong đó 𝜏 = 𝑗 − 𝑖 (𝑚𝑜𝑑 𝑝). Theo tiên đề 1, trong một chu kỳ số số 0 và số số 1 khác nhau chỉ 1 đơn vị nên trong 𝐵𝑘 ≠ 𝐵0 sẽ có 𝑝−1 2 số 1 và 𝑝+1 2 số (-1) nên từ 𝐵𝑖⨂𝐵𝑖+𝜏 = 𝐵𝑘, ta có: ∑ 𝑏𝑗𝑏𝑗+𝑟 = 1. 𝑝−1 2 + (−1) 𝑝+1 2 𝑝 𝑗=1 = −1 với 𝜏 ≠ 0 (mod p) Như vậy rõ ràng 𝐶𝑟 = 1 𝑝 ∑𝑏𝑛𝑏𝑛+𝑟 = { 1 𝜏 = 0 − 1 𝑝 𝜏 ≠ 0 (𝑚𝑜𝑑 𝑝) 𝑝 𝑛−1 Từ định lý trên chúng ta thấy M-dãy tạo thành từ các thanh ghi dịch tuyến tính phản hồi là ngẫu nhiên theo định nghĩa Blom. III.4.5. Chu kỳ của dãy nghi dịch tuyến tính và điều kiện M – dãy III.4.5.1. Hàm đặc trưng, đa thức đặc trưng của dãy ghi dịch a. Hàm đặc trưng Giả sử có thanh ghi dịch tuyến tính bậc r với hàm phản hồi tuyến tính: 𝐹 = 𝑓(𝑎0, 𝑎1, , 𝑎𝑟−1) = ∑ 𝑐𝑖𝑎𝑟−𝑖 = 𝑟 𝑖=1 ar Với ai, ci GF(2), ci ( 1, ,n ) gọi là các hệ số phản hồi, ai là giá trị tại ô thứ i của thanh ghi. Khi đó: Định nghĩa: Cho dãy ghi dịch {an} = a0, a1, a2, được sinh bởi thanh ghi dịch F. Khi đó, đa thức: 𝐺(𝑥) = ∑ 𝑎𝑛𝑥 𝑛∞ 𝑛=0 được gọi là hàm đặc trưng của dãy {𝑎𝑛}. Chú ý rằng ở đây trạng thái đầu của thanh ghi dịch được xem như {𝑎−1, 𝑎−2, , 𝑎−𝑟} Thang Long University Libraty 54 b. Đa thức đặc trưng Bây giờ giả sử dãy 𝑎𝑛 = ∑ 𝑐𝑖𝑎𝑛−𝑖 𝑟 𝑖=1 khi đó 𝐺(𝑥) = ∑(∑𝑐𝑖𝑎𝑛−𝑖 𝑟 𝑖=1 )𝑥𝑛 =∑𝑐𝑖𝑥 𝑖 𝑟 𝑖=1 (∑𝑎𝑛−𝑖𝑥 𝑛−𝑖 ∞ 𝑛=0 ) ∞ 𝑛=0 =∑𝑐𝑖𝑥 𝑖 𝑟 𝑖=1 [𝑎−𝑖𝑥 −𝑖 +⋯+ 𝑎−1𝑥 −1 +∑𝑎𝑛𝑥 𝑛 ∞ 𝑛=0 ] ∑𝑐𝑖𝑥 𝑖(𝑎−𝑖𝑥 −𝑖 +⋯+ 𝑎−1𝑥 −1) + 𝑟 𝑖=1 ∑𝑐𝑖𝑥 𝑖 𝑟 𝑖=1 𝑎(𝑥) → 𝐺(𝑥) [1 −∑𝑐𝑖𝑥 𝑖 𝑟 𝑖=1 ] = ∑𝑐𝑖𝑥 𝑖(𝑎−𝑖𝑥 −𝑖 +⋯+ 𝑎−1𝑥 −1) 𝑟 𝑖=1 Và vì vậy 𝐺(𝑥) = ∑ 𝑐𝑖𝑥 𝑖(𝑎−𝑖𝑥 −𝑖 +⋯+ 𝑎−1𝑥 −1)𝑟𝑖=1 1 − ∑ 𝑐𝑖𝑥𝑖 𝑟 𝑖=1 Định nghĩa : ký hiệu 𝑓(𝑥) = 1 − ∑ 𝑐𝑖𝑥 𝑖𝑟 𝑖=1 = 1 + ∑ 𝑐𝑖𝑥 𝑖𝑟 𝑖=1 trong trường hợp GF(2) thì f(x) chỉ phụ thuộc vào các hệ số phản hồi ci (i=1,2,,r). Do vậy f(x) được gọi là đa thức đặc trưng của dãy ghi dịch tuyến tính và dãy {𝑎𝑛} có được gọi là sinh bởi đa thức đặc trưng f(x) III.4.5.2. Chu kỳ của dãy ghi dịch tuyến tính. Các định lý sau đây cho ta cơ sở để xác định chu kỳ của một dãy ghi dịch tuyến tính theo hàm sinh của nó. Định lý : Giả sử dãy ghi dịch tuyến tính bậc r, {𝑎𝑛} sinh bởi đa thức f(x) với điều kiện ban đầu 𝑎−1 = 𝑎−2 = ⋯ = 𝑎−𝑟+1 = 0; 𝑎−𝑟 = 1 55 Khi đó chu kỳ của dãy {𝑎𝑛} sẽ là số 𝑝 ∈ 𝑁 nhỏ nhất sao cho f(x) là ước của (1 − 𝑥𝑝) (𝑚𝑜𝑑 2) Chứng minh: Biết rằng từ điều kiện ban đầu trên ta có: ∑𝑐𝑖𝑥 𝑖(𝑎−𝑖𝑥 −𝑖 +⋯+ 𝑎−1𝑥 −1) 𝑟 𝑖=1 = 𝑐𝑟 Tức là 𝐺(𝑥) = 𝑐𝑟 1 + ∑ 𝑐𝑖𝑥𝑖 𝑟 𝑖=1 = 𝑐𝑟 𝑓(𝑥) = ∑𝑎𝑛𝑥 𝑛 ∞ 𝑛=0 ở đây 𝑐𝑟 = 1 vì 𝑐𝑟 ∈ 𝐺𝐹(2) trước hết giả sử {𝑎𝑛} có chu kỳ p; khi đó ta có: 1 𝑓(𝑥) = 𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1 + 𝑥𝑝(𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1) + 𝑥2𝑝(𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1) = (𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1)(1 + 𝑥𝑝 + 𝑥2𝑝 +⋯) = (𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1). 1 1 − 𝑥𝑝 ⇒ 1−𝑥𝑝 𝑓(𝑥) = 𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1 Tức là f(x) là ước của 1 − 𝑥𝑝. Từ nay, ta ký hiệu 𝑓(𝑥)/( 1 − 𝑥𝑝) Bây giờ ta giả sử ngược lại 𝑓(𝑥)/( 1 − 𝑥𝑝). Thực hiện phép chia đa thức 1 − 𝑥𝑝 cho f(x) ta có: (1 − 𝑥𝑝) = 𝑓(𝑥). (𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1); 𝑎𝑖 ∈ 𝐺𝐹(2) Thành thử 𝑓(𝑥) = 1−𝑥𝑝 𝑎0+𝑎1𝑥+⋯+𝑎𝑝−1𝑥𝑝−1 ⇒ 𝐺(𝑥) = 1 𝑓(𝑥) = 𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1 1 − 𝑥𝑝 = (𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1)((1 + 𝑥𝑝 + 𝑥2𝑝 +⋯) Thang Long University Libraty 56 = 𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1 + 𝑥𝑝(𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1) + 𝑥2𝑝(𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1) + ⋯ ⇒ 𝐺(𝑥) = (𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1) + (𝑎0𝑥 𝑝 + 𝑎1𝑥 𝑝+1 +⋯+ 𝑎𝑝−1𝑥 2𝑝−1) + ⋯ Tức 𝐺(𝑥) = (𝑎0 + 𝑎1𝑥 +⋯+ 𝑎𝑝−1𝑥 𝑝−1) + (𝑎𝑝𝑥 𝑝 + 𝑎𝑝+1𝑥 𝑝+1 + ⋯+ 𝑎2𝑝−1𝑥 2𝑝−1) + ⋯ Với 𝑎𝑛+𝑘𝑝 = 𝑎𝑛 Từ biểu thức trên chứng tỏ chuỗi có chu kỳ p. Chú ý rằng: Từ chứng minh trên ta có: Do 𝐺(𝑥) = 𝜑(𝑥) 𝑓(𝑥) với bậc của 𝜑(𝑥) < bậc của 𝑓(𝑥) nên (𝑓, 𝜑) = 1 (𝜑 không là ước của f) thì định lý trên vẫn đúng. Nếu 𝑓(𝑥) = 1 + ∑ 𝑐𝑖𝑥 𝑖𝑟 𝑖=1 là bất khả quy (tức là không thể tách được 𝑓(𝑥) = 𝑆(𝑥). 𝑅(𝑥) với S(x) và R(x) là hai đa thức bậc nhỏ hơn r thì chu kỳ p cuả f(x) không phụ thuộc điều kiện ban đầu (trừ trường hợp , 𝜑(𝑥) = 0) Định lý : Nếu {𝑎𝑛} là M-dãy (có chu kỳ cực đại p=2 r-1 thì đa thức đặc trưng của nó 𝑓(𝑥) = 1 + ∑ 𝑐𝑖𝑥 𝑖𝑟 𝑖=1 là bất khả quy. Chứng minh: Giả sử {𝑎𝑛} là M-dãy bậc r, khi đó chu kỳ p=2 r-1, thành thử trong chu kỳ của nó phải chứa tất cả các r-tupel khác 0 tức là phải chứa r- tupel dạng 1 0 0 00⏟ r−1 bít 0 . Lấy r-tupel trên làm điều kiện ban đầu ta được kết quả đã nói trong định lý 1, tức là chu kỳ của dãy sẽ là số tự nhiên nhỏ nhất sao cho 𝑓(𝑥) là ước của (1-xp). Bây giờ giả sử rằng f(x) không là bất khả quy, khi đó: 𝑓(𝑥) = 𝑆(𝑥). 𝑅(𝑥) với (S(x),R(x))=1, và do vậy: 57 1 𝑓(𝑥) = 𝛼(𝑥) 𝑆(𝑥) + 𝛽(𝑥) 𝑅(𝑥) Giả sử bậc của S(x) là r1, của R(x) là r2 với r1+r2=r. Như vậy, 𝛼(𝑥) 𝑆(𝑥) sẽ là hàm sinh của dãy có chu kỳ 𝑃1 ≤ 2 𝑟 − 1 và 𝛽(𝑥) 𝑅(𝑥) cũng là hàm sinh của dãy có chu kỳ là bội số chung nhỏ nhất của hai chu kỳ trên. Như vậy 2𝑟 − 1 ≤ (2𝑟1 − 1)(2𝑟2 − 1) = 2𝑟1+𝑟2 − 2𝑟1 − 2𝑟2 + 1 ≤ 2𝑟 − 2 − 2 + 1 = 2𝑟 + 3 Điều đó mâu thuẫn. Do vậy, f(x) phải là đa thức bất khả quy – Định lý được chứng minh. Chú ý: - Điều kiện bất khả quy của f(x) chỉ là điều kiện cần tức là có những đa thức là bất khả quy nhưng không tạo thành M - dãy. Ví dụ: 𝑓1(𝑥) = 𝑥 4 + 𝑥3 + 𝑥2 + 𝑥 + 1 là bất khả quy và là đa thức đặc trưnng của dãy có chu kỳ là 5 vì f(x) là ước của (1-x5). Trong khi đó chu kỳ cực đại của dãy là 24-1=15 hoặc giả 𝑓2(𝑥) = 𝑥 6 + 𝑥3 + 1 là ước của (1-x9). Nếu dãy có đa thức đặc trưng f(x) là bất khả quy bậc r thì chu kỳ của dãy sẽ là ước cuả 2r-1. Do vậy nếu (2r-1) là số nguyên tố Mecxen (Mersenne) thì mọi đa thức bất khả quy bậc r đều tạo M-dãy. Về điều kiện của M – dãy ta có định lý tổng quát sau: Định lý: Nếu đa thức đặc trưng f(x) trong GF(q) nguyên thủy bậc n thì mọi dãy khác không sinh ra bởi nó có chu kỳ T = qn – 1 Chứng minh: Do f(x) là nguyên thủy mà f(x) là ước của 𝑥𝑞 𝑛−1 – 1 do vậy chu kỳ của dãy khác không sinh ra bởi nó phải là ước của qn – 1. Giả sử rằng chu kỳ Thang Long University Libraty 58 T< qn–1 . Khi đó dãy phải được sinh ra bởi ( xT – 1 ) tức là f(x) phải là ước của ( xT – 1 ) điều đó trái với giả thiết f(x) là nguyên thủy bậc n. Như vậy chu kỳ của dãy phải là qn – 1 , tức là f(x) sinh ra M – dãy ( dãy có chu kỳ cực đại ). Số các đa thức nguyên thủy Primitive tạo M-dãy bậc r là: 𝜆(𝑥) = ⌈𝛷(2𝑟 − 1)⌉ 𝑟 Ở đây Φ(. ) là hàm ơle mà giá trị của nó bằng số các số nguyên dương nhỏ hơn n và nguyên tố với n. ví dụ: Với r = 4 thì 𝛷(24 − 1)=Φ(15) = 7 Vậy 𝜆(4) = ⌈𝛷(15)⌉ 𝑟4 = ⌈ 7 4 ⌉ = 2 tính toán cụ thể được theo bảng dưới đây R λ(r) r λ(r) 5 6 9 48 6 8 10 60 7 18 16 2048 8 32 Rõ dàng số lượng các M – dãy khá nhỏ, vì vậy trong thực tế thường sử dụng các dãy tạo thành bằng cách “ cộng “ một số M – dãy để được các dãy mới có chu kì lớn và số M – dãy tăng. Ví dụ bằng phương pháp thích hợp thì với r = 10, số các M – dãy có thể lên tới 388 000. Việc nghiên cứu tạo các dãy có chu kì và số lượng M – dãy lớn là mục đích của nhiều ứng dụng khác nhau. Đặc biệt là trong các vấn để bảo vệ thông tin nói chung và mật mã nói riêng. 59 III.4.6. Hàm tự tương quan Để xác định tính phụ thuộc (hay độc lập) giữa các phần tử của một dãy giả ngẫu nhiên, người ta sử dụng khái niệm tự tương quan mà vai trò và tính chất của nó cũng không khác đáng kể so với hàm tự tương quan trong lý thuyết các quá trình ngẫu nhiên. a. Định nghĩa: Hàm tự tương quan của một dãy ngẫu nhiên {x0, x1, xn} có chu kỳ T được xác định bởi: A(j) = 1 𝑟 ∑𝑥𝑖𝑥𝑖+𝑗 𝑇−1 𝑗=0 Trong đó xi là phần tử thứ I và T là chu kỳ của dãy. Ví dụ: Dãy 𝑥𝑖 = { 0 1 𝑣ớ𝑖 𝑖 ≠ 𝑚𝑇 𝑣ớ𝑖 𝑖 = 𝑚𝑇 m = 0, 1, 2, k Khi đó hàm tự tương quan A(j) = { 1 𝑇 𝑣ớ𝑖 𝑗 = 0, 𝑇, 2𝑇 0 𝑣ớ𝑖 𝑗 𝑐ò𝑛 𝑙ạ𝑖 b. Tính chất của hàm tự tương quan với dãy giả ngẫu nhiên nhị phân có chu kỳ cực đại. Biết rằng mỗi dãy giả ngẫu nhiên nhị phân có chu kỳ cực đại T = 2n – 1 (m – dãy) chứa đúng 2n – 1 số 0 và 2n-1 số 1. Từ đó suy ra định lý sau: Định lý: Dãy có chu kỳ cực đại sinh bởi đa thức sinh f(n) cấp n, có hàm tự tương quan xác định bởi: A(j) = ∑ 𝐵(𝑥𝑖+𝑥𝑖+𝑗) 2𝑛−1 𝑖=0 Trong đó: B(0) = +1, B(1) = -1. Khi đó: Thang Long University Libraty 60 A(j) = { 2𝑛 − 1 𝑛ế𝑢 (2𝑛 − 1)|𝑟 −1 𝑡𝑟𝑜𝑛𝑔 𝑡𝑟ườ𝑛𝑔 ℎợ𝑝 𝑛𝑔ượ𝑐 𝑙ạ𝑖 Thật vậy: nếu ta dịch chuyển dãy xi(i=0, 1, 2, , 2n-1) đi một bước độ dài r để được dãy xi+r(i=0, 1, 2, , 2n-1) mới hoặc là cùng loại với dãy cũ, hoặc chỉ khác một dịch chuyển vòng. Trong trường hợp đầu thì tổng giá trị của B sẽ là -1 vì nó chứa 2n-1-1 số 0 và 2n-1 số 1. Trong trường hợp sau, tất cả đều bằng 1 thành thử giá trị của B là 2n-1-1. Ví dụ: đa thức nguyên thủy f(x) = x3 + x + 1 sinh ra dãy số có chu kỳ T = 23 – 1 = 7. Đó là 1010011|1010011|101.. Đa thức nguyên thủy bậc 20 trên Z2 x20 + x3 + 1 sẽ sinh ra dãy giả ngẫu nhiên với chu kỳ 220 – 1 ≈ 106. Hàm A(j) sẽ bằng -1 với tất cả các giá trị j bằng bội của 106 và bằng 220 – 1 trong các trường hợp ngược lại. III.4.7. Một vài ví dụ về dãy ghi dịch chu kỳ cực đại Ví dụ 1: Đa thức đặc trưng f(x) = x4 + x3 + 1 là đa thức nguyên thủy vì là ước của đa thức x15 + 1 nhưng không là ước của các đa thức xk + 1 với k<15 trong Z2. Khi đó một trong các dãy nhị phân mà nó sinh ra có dạng: 10001001101011110001 Có chu kỳ T = 15 = 24 – 1. Dễ dàng thấy rằng trong chu kỳ của dãy trên, số chữ số 1 là 8, số chữ số 0 là 7, có thể coi như có phân phối xác xuất gần đều P(x = 0) = 7/15 ≈ P(x = 1) = 8/15. Ví dụ 2: Các đa thức nguyên thủy bậc 5, 6, 7, 15, 23, 31 trên trường Z2 x5 + x3 + 1, x6 + x + 1, x7 + x6 + 1, x15 + x14 + 1, x23 + x15 + 1, x 31 + x25 + 1 sinh ra các dãy có chu kỳ tương ứng là 25 – 1, 26 – 1, 27 – 1, 215 – 1, 223 – 1, 231 – 1. 61 TÀI LIỆU THAM KHẢO 1- Lý Hoàng Tú (2003). Phân tích chuỗi thời gian. NXB Thống Kê – Hà Nội 1; 2- Nguyễn Công Sứ (1998). Quá trình ngẫu nhiên và vật lý thông tin ứng dụng – Lưu hành nội bộ - Học viện kỹ thuật mật mã ; 3- Lều Đức Tân(2001). Khóa ngẫu nhiên và phương pháp thực nghiệm đánh giá ngẫu nhiên của khóa – Lưu hành nội bộ học viện mật mã, Hà nội; 4- Trần Xuân Trường (2001). Dãy ngẫu nhiên trong mật mã – Lưu hành nội bộ - Học viện kỹ thuật mật mã, Hà Nội. 5- Cơ sở mật mã hiện đại (2004 )(Dịch từ tiếng Nga – Lưu hành nội bộ Ban cơ yếu Chính Phủ), Hà Nội 9; 6- Xiraep (1980). Xác xuất (bản tiếng Nga) – Matxcova; 7- K.nut (1997). Nghệ thuật lập trình cho máy tính (bản tiếng Nga) – Matxcova; 8- Mật mã học và các mật mã tốc độ cao (bản tiếng Nga)( 2002) . NXB Khoa Học Xanh-petecbua.; 9- L.Blum, M.Blum and M. Shub - A simple unpredictable pseudorandom number generator. SIAM Journal Comp, Vol 15, 1986, pp 364-383; 10- D. Knuth – The art of computer programming: Vol 2. Seminumerical algorithms, 2nd editon addison-Wesley, 1981. 11- Modezn Afplied and Thomas C.Bartee ( bản tiếng Nga) (1976). Moskow. Thang Long University Libraty