Phát hiện chu trình

Trong Khoa học máy tính, bài toán phát hiện chu trình hay tìm chu trình là bài tìm thuật toán tìm vòng lặp trong một chuỗi giá trị hàm.

Bất kỳ hàm $f$ nào ánh xạ một tập hữu hạn $S$ tới chính nó, và bất kỳ giá trị ban đầu $x_{0}$ trong $S$ , chuỗi các giá trị hàm

x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots

phải có một giá trị xuất hiện hai lần: có một số cặp i và j phân biệt sao cho $x_{i}=x_{j}$ . Khi điều này xảy ra, chuỗi tiếp tục chu trình một cách định kỳ, bằng cách lặp lại chuỗi giá trị từ $x_{i}$ tới $x_{j-1}$ . Tìm chu trình là bài toán tìm i và j khi biết $f$ và $x_{0}$ .

Rất nhiều thuật toán tìm chu trình nhanh và dùng ít bộ nhớ được biết. Thuật toán rùa và thỏ của Robert W.Floyd di chuyển hai con trỏ với vận tốc khác nhau qua chuỗi cho đến khi chúng cùng chỉ một giá trị. Lựa chọn khác, ta có thuật toán của Brent dựa trên ý tưởng tìm kiếm theo cấp số mũ. Cả hai thuật toán trên chỉ dùng một số lượng cố định bộ nhớ và tính giá trị hàm một lượng tỷ lệ thuận với khoảng cách tính từ xuất phát của chuỗi đến giá trị lặp đầu tiên. Các thuật toán khác đổi bộ nhớ lớn hơn để tính ít hơn số lần tính giá trị hàm.

Ứng dụng của phát hiện chu trình bao gồm thử nghiệm chất lượng của bộ sinh số giả ngẫu nhiên và hàm băm mật mã học, các thuật toán trong lý thuyết số tính toán, phát hiện vòng lặp vô hạn trong các chương trình máy tính và các cấu hình tuần hoàn trong tế bào tự động hóa.

Thí dụ[sửa | sửa mã nguồn]

Hình bên cho biết một hàm $f$ ánh xạ tập $S=\{0,1,2,3,4,5,6,7,8\}$ tới chính nó. Nếu ta xuất phát từ $x_{0}=2$ và liên tục áp dụng hàm $f$ , ta sẽ được chuỗi sau

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

Chu trình trong chuỗi giá trị này là 6, 3, 1.

Định nghĩa[sửa | sửa mã nguồn]

Gọi $S$ là tập hữu hạn bất kỳ, $f$ là hàm bất kỳ từ $S$ ánh xạ vào chính nó và $x 0$ là phần tử bất kỳ trong $S$ . Với bất kỳ $i > 0$ , đặt $x i = f (x i - 1)$ . Gọi $μ$ là chỉ số nhỏ nhất sao cho giá trị $x μ$ thường xuyên lặp lại vô hạn trong chuỗi giá trị $x i$ và đặt $λ$ (độ dài vòng lặp) là số nguyên dương nhỏ nhất sao cho $x μ = x λ + μ$ . Bài toán phát hiện chu trình yêu cầu tìm hai giá trị $λ$ và $μ$ .^[1]

Ta có thể xét bài toán này bằng lý thuyết đồ thị, bằng cách xây một đồ thị hàm (một đồ thị có hướng mà mỗi đỉnh có một cung đi ra) trong đó mỗi đỉnh là một phần tử của S, và các cung đi ra ánh xạ phần tử giá trị hàm tương ứng, như hình trên.

Các thuật toán[sửa | sửa mã nguồn]

Nếu input được đưa như một thủ tục con là để tìm f, bài toán có thể giải đơn giản dùng chỉ $\lambda +\mu$ lần tính hàm, bằng cách tính chuỗi giá trị $x_{i}$ dùng một cấu trúc dữ liệu như bảng băm để lưu các giá trị này và kiểm tra xem các giá trị sau đã được lưu chưa. Tuy nhiên, độ phức tạp bộ nhớ tỉ lệ thuận với $\lambda +\mu$ , lớn không cần thiết. Do đó nghiên cứu trong khu vực này tập trung vào hai mục tiêu: dùng ít bộ nhớ hơn thuật toán trên và tìm thuật toán con trỏ dùng ít số lần kiểm tra hơn.

Thuật toán rùa và thỏ của Floyd[sửa | sửa mã nguồn]

Thuật toán tìm chu trình của Floyd là thuật toán con trỏ dùng hai con trỏ, di chuyển trên cùng một chuỗi với tốc độ khác nhau. Nó cũng được gọi là "thuật toán rùa và thỏ", dựa trên câu chuyện ngụ ngôn của Aesop.

Thuật toán được đặt tên theo Robert W. Floyd, người được công nhận bởi Donald Knuth.^[2]^[3] Tuy nhiên, thuật toán không xuất hiện trong các bài của Floyd, và do đó đây có thể là quy kết nhầm: Floyd mô tả các thuật toán liệt kê toàn bộ các chu trình đơn trong một đồ thị có hướng trong tờ nghiên cứu năm 1967,^[4] nhưng tờ báo đó không mô tả bài toán tìm chu trình với đồ thị hàm ở đây. Thậm chí, theo lời của Knuth (vào năm 1969), quy nó về Floyd mà không trích dẫn.^[5]

Yếu tố quan trọng trong thuật toán như sau. Nếu có một chu trình, thì, với bất kỳ $i \geq μ$ và $k \geq 0$ , $x i = x i + kλ$ , với $λ$ là độ dài vòng lặp cần tìm và $μ$ là vị trí của phần tử đầu tiên trong chu trình. Dựa trên đây, ta có thể chứng minh $i = kλ \geq μ$ với một vài số $k$ khi và chỉ khi $x i = x 2 i$ . Như vậy, thuật toán chỉ cần kiểm tra các giá trị lặp lại dưới dạng đặc biệt trên, với một con trỏ để cách gấp đôi từ vị trí xuất phát, để tìm chu kỳ $ν$ cho một lần lặp là bội của $λ$ . Một khi $ν$ được tìm thấy, thuật toán tìm ngược lại từ lúc ban đầu để tìm giá trị đầu tiên $x μ$ trong chuỗi, khi biết rằng $λ$ là ước của $ν$ và do đó $x μ = x μ + v$ . Cuối cùng, một khi $μ$ đã được biết, bài toán trở nên đơn giản trong việc tìm độ dài $λ$ cho chu trình lặp lại ngắn nhất, bằng việc tìm vị trí đầu tiên của $μ + λ$ sao cho $x μ + λ = x μ$ .

Thuật toán do đó dùng hai con trỏ, con trỏ đầu tiên (con rùa) nằm tại $x i$ , và con còn lại (con trỏ) nằm tại $x 2 i$ . Trong mỗi bước của thuật toán, tăng $i$ bởi một, di chuyển con rùa một bước phía trước và con thỏ hai bước phía trước trong chuỗi, rồi so sánh giá trị chuỗi ở hai con trỏ này. Giá trị nhỏ nhất của $i > 0$ sao cho rùa và thỏ đều trỏ vào cùng một giá trị là giá trị $ν$ cần tìm.

Đoạn code Python sau mô tả ý tưởng thuật toán trên:

def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

Thuật toán chỉ dùng con trỏ để lưu và sao chép giá trị, tính giá trị hàm và kiểm tra bằng nhau, do đó nó thỏa mãn yêu cầu của thuật toán con trỏ.Thuật toán dùng $O (λ + μ)$ số phép tính trên, và $O (1)$ bộ nhớ.^[6]

Thuật toán của Brent[sửa | sửa mã nguồn]

Richard P. Brent mô tả một thuật toán tìm chu trình khác, giống thuật toán rùa và con thỏ, chỉ cần hai con trỏ để duyệt dãy số.^[7] Tuy nhiên, nó dựa theo nguyên tắc khác: tìm giá trị lũy thừa bậc hai nhỏ nhất $2 i$ mà lớn hơn cả $λ$ và $μ$ . Với $i = 0, 1, 2, ...$ , thuật toán so sánh $x 2 i -1$ với mỗi giá trị phần tử tiếp theo cho đến khi gặp lũy thừa bậc hai tiếp theo, dừng khi nó gặp một cặp bằng nhau. Thuật toán có hai ưu thế so với thuật toán rùa và con thỏ: nó tìm đúng và trực tiếp giá trị $λ$ của chu trình, thay vì phải tìm nó trong đoạn mã sau, và các bước của nó chỉ cần một phép tính $f$ hơn là 3.^[8]

Đoạn code python sau mô tả lại ý tưởng trên.

def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:  # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Find the position of the first repetition of length λ
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed until they agree
    mu = 0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu

Giống thuật toán rùa và thỏ, đây là thuật toán con trỏ dùng $O (λ + μ)$ lần kiểm tra và tính hàm cùng với $O (1)$ bộ nhớ. Đồng thời cũng không quá khó để chứng minh rằng số lần tính hàm không bao giờ cao hơn số lần tính trong thuật toán của Floyd. Brent cho rằng, trên trung bình, thuật toán tìm chu trình của ông chạy khoảng 36% nhanh hơn so với cái của Floyd và nó đẩy tốc độ cho thuật toán Pollard rho bởi tầm 24%. Ông cũng xét phân tích trung bình cho phiên bản ngẫu nhiên của thuật toán trong đó dãy chỉ số xét bởi con trỏ chậm hơn không phải lũy thừa bậc hai như thường, mà là bội ngẫu nghiên của lũy thừa bậc hai. Mặc dù ông định áp dụng chủ yếu cho các thuật toán phân tích số nguyên, Brent cũng có xét tới các ứng dụng cho việc kiểm nghiệm các bộ sinh số giả ngẫu nhiên.^[7]

Tham khảo[sửa | sửa mã nguồn]

^ Joux, Antoine (2009), Algorithmic Cryptanalysis, CRC Press, tr. 223, ISBN 9781420070033.
^ Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, tr. 7, exercises 6 and 7
^ Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others
^ Floyd, R.W. (1967), “Nondeterministic Algorithms”, J. ACM, 14 (4): 636–644, doi:10.1145/321420.321422, S2CID 1990464
^ The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8
^ Joux (2009), Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.
^ ^a ^b Brent, R. P. (1980), “An improved Monte Carlo factorization algorithm” (PDF), BIT Numerical Mathematics , 20 (2): 176–184, doi:10.1007/BF01933190, S2CID 17181286, Bản gốc (PDF) lưu trữ ngày 24 tháng 9 năm 2009, truy cập ngày 9 tháng 9 năm 2021.
^ Joux (2009), Section 7.1 .2, Brent's cycle-finding algorithm, pp. 226–227.

[1] Joux, Antoine (2009), Algorithmic Cryptanalysis, CRC Press, tr. 223, ISBN 9781420070033.

[knuth-2] Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, tr. 7, exercises 6 and 7

[3] Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others

[4] Floyd, R.W. (1967), “Nondeterministic Algorithms”, J. ACM, 14 (4): 636–644, doi:10.1145/321420.321422, S2CID 1990464

[5] The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8

[6] Joux (2009), Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.

[brent-7] Brent, R. P. (1980), “An improved Monte Carlo factorization algorithm” (PDF), BIT Numerical Mathematics , 20 (2): 176–184, doi:10.1007/BF01933190, S2CID 17181286, Bản gốc (PDF) lưu trữ ngày 24 tháng 9 năm 2009, truy cập ngày 9 tháng 9 năm 2021.

[8] Joux (2009), Section 7.1 .2, Brent's cycle-finding algorithm, pp. 226–227.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]