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ó.

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

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. . Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996.
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.
&x7C;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)
by Stephan Lavavej (Microsoft, 2013)