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

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

Bộ sinh số giả ngẫu nhiên (pseudorandom number generator - 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ửứ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."[2]

Tính tuần hoàn[sửa | sửa mã nguồn]

Vấn đề tiềm ẩn của bộ sinh số tất định[sửa | sửa mã nguồn]

Bộ sinh số dựa trên sự lặp lại tuyến tính[sửa | sửa mã nguồn]

Bộ sinh số giả ngẫu nhiên đảm bảo an toàn mật mã[sửa | sửa mã nguồn]

Tiêu chuẩn đánh giá BSI[sửa | sửa mã nguồn]

Định nghĩa toán học[sửa | sửa mã nguồn]

Cách tiếp cận thưở ban đầu[sửa | sửa mã nguồn]

Bộ sinh số không đồng nhất[sửa | sửa mã nguồn]

Xem thêm[sửa | sửa mã nguồn]

  • 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[sửa | sửa mã nguồn]

  1. ^ “Pseudorandom number generators”. Khan Academy. Truy cập ngày 11 tháng 1 năm 2016. 
  2. ^ Chú thích trống (trợ giúp) 

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

  • 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.  |tựa đề= 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[sửa | sửa mã nguồn]