Bộ sinh số giả ngẫu nhiên

Bộ sinh số giả ngẫu nhiên (pseudorandom number generator hay còn gọi là PRNG), còn được gọi là bộ sinh bit ngẫu nhiên tất định (DRBG), là thuật toán sinh ra chuỗi các số có các thuộc tính gần như thuộc tính của chuỗi số ngẫu nhiên. Chuỗi sinh ra từ bộ sinh số giả ngẫu nhiên không thực sự là ngẫu nhiên, do nó hoàn toàn được xác định từ giá trị khởi đầu, được gọi là nguồn (seed) của nó (mà giá trị này có thể hoàn toàn là ngẫu nhiên). Mặc dù chuỗi gần ngẫu nhiên này gần giống với chuỗi được sinh ra bằng bộ sinh số ngẫu nhiên phần cứng, bộ sinh số giả ngẫu nhiên có vai trò rất quan trọng trong thực tế vì tốc độ trong quá trình tạo số và khả năng tái sử dụng của nó.^[1]

Các bộ sinh số giả ngẫu nhiên là trung tâm trong các ứng dụng như giả lập (ví dụ phương pháp Monte Carlo), các trò chơi điện tử và ứng dụng mật mã. Các ứng dụng mật mã đòi hỏi kết quả đầu ra ở sau không thể dự đoán được bằng đầu ra trước đó, và các thuật toán phức tạp hơn mà không có tính tuyến tính như các bộ sinh số giả ngẫu nhiên đơn giản.

Đặc tính thống kê tốt là yêu cầu chính đối với đầu ra của bộ sinh số giả ngẫu nhiên. Nhìn chung, để tự tin rằng bộ sinh số giả ngẫu nhiên tạo ra chuỗi các sổ đủ ngẫu nhiên phù hợp với yêu cầu thì việc phân tích toán học cẩn thận là điều cần thiết. John von Neumann đã lên tiếng cảnh báo việc xem bộ sinh số giả ngẫu nhiên như là bộ sinh số thực sự ngẫu nhiên, và nói đùa rằng "Bất cứ ai truy xét các phương pháp số học của việc tạo ra các số ngẫu nhiên đều là tội phạm phạm."

Tính tuần hoàn

Vấn đề tiềm ẩn của bộ sinh số tất định

Bộ sinh số dựa trên sự lặp lại tuyến tính

Bộ sinh số giả ngẫu nhiên đảm bảo an toàn mật mã

Tiêu chuẩn đánh giá BSI

Định nghĩa toán học

Cách tiếp cận thuở ban đầu

Bộ sinh số không đồng nhất

Xem thêm

• Danh sách các bộ sinh số giả ngẫu nhiên
• Ứng dụng của tính ngẫu nhiên https://en.wikipedia.org/wiki/Applications_of_randomness
• Chuỗi có tính khác biệt thấp
• Chuỗi nhị phân giả ngẫu nhiên
• Tiếng ồn giả ngẫu nhiên
• Tạo số ngẫu nhiên
• Tấn công bộ sinh số giả ngẫu nhiên
• Ngẫu nhiên
• Ngẫu nhiên thống kê

Tham khảo

1. “Pseudorandom number generators”. Khan Academy. Truy cập ngày 11 tháng 1 năm 2016.

Tham khảo

• Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST SP800-90A, January 2012
• Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
• Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
• Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
• Knuth D.E.. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
• Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. ISBN 9780691025469
• von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
• . ISBN 0-471-16449-6. |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
• Viega J., "Practical Random Number Generation in Software", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

Liên kết ngoài

• TestU01: A free, state-of-the-art (GPL) C++ Random Number Test Suite.
• DieHarder: A free (GPL) C Random Number Test Suite.
• "Generating random numbers" (in embedded systems) by Eric Uner (2004)
• "Analysis of the Linux Random Number Generator" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
• "Better pseudorandom generators" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)
• rand() Considered Harmful trên YouTube by Stephan Lavavej (Microsoft, 2013)