Máy tạo số ngẫu nhiên không quốc tịch có tồn tại không?

Question

Có sự khác biệt nào giữa việc tạo nhiều số bằng cách sử dụng một trình tạo số ngẫu nhiên đơn (RNG) so với việc tạo ra một số cho mỗi trình tạo và loại bỏ nó không? Cả hai cách triển khai có tạo ra các số ngẫu nhiên không? Có sự khác biệt giữa RNG bình thường và RNG an toàn cho điều này không?

Tôi có ứng dụng web được tạo danh sách các số ngẫu nhiên thay mặt cho khách hàng. Tức là, các con số sẽ xuất hiện ngẫu nhiên theo quan điểm của từng khách hàng. Điều này có nghĩa là tôi cần giữ lại RNG ngẫu nhiên riêng biệt cho mỗi phiên của khách hàng không? Hoặc tôi có thể chia sẻ một RNG duy nhất trên tất cả các phiên không? Hoặc tôi có thể tạo và loại bỏ RNG trên cơ sở theo yêu cầu không?

CẬP NHẬT: Câu hỏi này có liên quan đến Is a subset of a random sequence also random?

Answer 1

Trình tạo số ngẫu nhiên có trạng thái - đó thực sự là một tính năng cần thiết. Số "ngẫu nhiên" tiếp theo là hàm của số trước và hạt/trạng thái. Người thuần túy gọi họ là những người tạo số giả ngẫu nhiên. Các con số sẽ vượt qua các bài kiểm tra thống kê cho sự ngẫu nhiên, nhưng không thực sự - ngẫu nhiên.

Chuỗi các giá trị ngẫu nhiên là hữu hạn và không lặp lại.

Hãy nghĩ đến trình tạo số ngẫu nhiên khi xáo trộn một tập hợp các số và sau đó xử lý chúng theo thứ tự ngẫu nhiên. Hạt giống được sử dụng để "trộn" các số. Khi hạt giống được đặt, chuỗi số được cố định và rất khó dự đoán. Một số hạt sẽ lặp lại sớm hơn những hạt khác.

Hầu hết các máy phát có khoảng thời gian đủ dài để không ai nhận thấy nó lặp lại. Một bộ tạo số ngẫu nhiên 48 bit sẽ tạo ra vài trăm tỷ số ngẫu nhiên trước khi nó lặp lại - với (AFAIK) bất kỳ giá trị hạt 32 bit nào.

Máy phát sẽ chỉ tạo các giá trị giống như ngẫu nhiên khi bạn cho nó một hạt giống duy nhất và để cho nó tăng giá trị. Nếu bạn thay đổi hạt giống, thì số được tạo với giá trị hạt giống mới có thể không xuất hiện ngẫu nhiên khi so sánh với các giá trị được tạo bởi hạt trước đó - tất cả các cược sẽ tắt khi bạn thay đổi hạt giống. Vì vậy, không.

Cách tiếp cận âm thanh là có một máy phát và "xử lý" các con số xung quanh với các khách hàng khác nhau của bạn. Đừng gây rối với việc tạo và loại bỏ máy phát điện. Đừng làm thay đổi hạt giống.

Trên tất cả, không bao giờ cố gắng viết trình tạo số ngẫu nhiên của riêng bạn. Các máy phát tích hợp trong hầu hết các thư viện ngôn ngữ thực sự tốt. Đặc biệt là những cái hiện đại sử dụng hơn 32 bit.

Một số bản phân phối Linux có thiết bị /dev/random và /dev/urandom. Bạn có thể đọc chúng một lần để tạo trình tạo số ngẫu nhiên cho ứng dụng của bạn. Chúng có giá trị ngẫu nhiên nhiều hơn hoặc ít hơn, nhưng chúng hoạt động bằng cách "thu thập nhiễu" từ các sự kiện hệ thống ngẫu nhiên. Sử dụng chúng một cách tiết kiệm để có rất nhiều sự kiện ngẫu nhiên giữa các lần sử dụng.

Answer 2

Vâng, miễn là họ là hạt giống khác nhau mỗi khi họ đang tạo ra, sau đó không, tôi không nghĩ rằng có muốn được bất kỳ sự khác biệt; tuy nhiên, nếu nó phụ thuộc vào một cái gì đó như thời gian, sau đó họ có lẽ sẽ không thống nhất, do hạt giống thiên vị.

Answer 3

Tôi khuyên bạn nên sử dụng một trình tạo đơn nhiều lần. Theo như tôi biết, tất cả các máy phát điện đều có trạng thái. Khi bạn gieo một máy phát điện, bạn thiết lập trạng thái của nó thành một cái gì đó dựa trên hạt giống. Nếu bạn tiếp tục sinh sản những cái mới, có khả năng là những hạt giống bạn chọn sẽ không được như ngẫu nhiên như những con số được tạo ra bằng cách sử dụng chỉ một máy phát điện.

Điều này đặc biệt đúng với hầu hết các máy phát điện tôi đã sử dụng, sử dụng thời gian hiện tại tính bằng mili giây làm hạt.

Answer 4

Nếu bạn tạo RNG và tạo một số ngẫu nhiên duy nhất từ ​​nó thì loại bỏ RNG, số được tạo ra chỉ là ngẫu nhiên như hạt giống được sử dụng để khởi động RNG.

Sẽ tốt hơn nếu tạo một RNG và vẽ nhiều số từ nó.

Answer 5

Nói chung tốt hơn là tạo một PRNG đơn và kéo nhiều giá trị từ nó. Tạo nhiều cá thể có nghĩa là bạn cần đảm bảo rằng các hạt giống cho các cá thể được đảm bảo duy nhất, điều này sẽ yêu cầu kết hợp thông tin cá thể cụ thể.

Như một sang một bên, các trình tạo số ngẫu nhiên "thật" tốt hơn, nhưng chúng thường yêu cầu phần cứng chuyên dụng thực hiện các dữ liệu ngẫu nhiên từ phương sai tín hiệu điện bên trong máy tính. Trừ khi bạn đang thực sự lo lắng về nó, tôi muốn nói Pseudo Random Number Generator được xây dựng trong các thư viện ngôn ngữ và/hoặc hệ điều hành có lẽ là đủ, miễn là giá trị hạt giống của bạn không dễ dự đoán được.

Answer 6

Như mọi người đã nói, tốt hơn nên gieo hạt PRNG một lần và tái sử dụng nó. PRNG an toàn chỉ đơn giản là một ứng dụng phù hợp cho các ứng dụng mã hóa. Cách duy nhất tái gieo giống mỗi lần sẽ cho kết quả ngẫu nhiên hợp lý là nơi nó xuất phát từ một nguồn "thực sự" ngẫu nhiên - tức là phần cứng chuyên dụng. Thậm chí sau đó, có thể là nguồn là thiên vị và nó vẫn sẽ được về mặt lý thuyết tốt hơn để sử dụng cùng một PRNG hơn.

Answer 7

Thông thường việc gieo hạt một trạng thái mới sẽ mất khá nhiều thời gian cho một PRNG nghiêm trọng và tạo ra những cái mới mỗi lần sẽ không thực sự giúp ích gì nhiều. Trường hợp duy nhất tôi có thể nghĩ đến nơi bạn có thể muốn nhiều hơn một PRNG cho các hệ thống khác nhau, nói trong trò chơi sòng bạc, bạn có một máy phát điện để xáo trộn thẻ và một thẻ riêng biệt để tạo chú thích được thực hiện bởi các ký tự điều khiển máy tính. người dùng chuyên dụng không thể đoán kết quả dựa trên hành vi của nhân vật.

Một giải pháp tốt cho việc gieo hạt là sử dụng this (Random.org), chúng cung cấp các số ngẫu nhiên được tạo ra từ tiếng ồn không khí miễn phí.Nó có thể là một nguồn tốt hơn cho việc gieo giống hơn là sử dụng thời gian.

Chỉnh sửa: Trong trường hợp của bạn, tôi chắc chắn sẽ sử dụng một PRNG cho mỗi khách hàng, nếu không vì lý do nào khác ngoài các tiêu chuẩn lập trình tốt. Dù sao nếu bạn chia sẻ một PRNG giữa các khách hàng, bạn vẫn sẽ cung cấp các giá trị giả ngẫu nhiên cho từng chất lượng, tương đương với chất lượng của PRNG. Vì vậy, đó là một lựa chọn khả thi nhưng có vẻ như một chính sách tồi để lập trình

Answer 8

Điều đáng nói đến là Haskell là ngôn ngữ cố gắng loại bỏ hoàn toàn trạng thái có thể thay đổi. Để đối chiếu mục tiêu này với các yêu cầu cứng như IO (yêu cầu một dạng biến đổi nào đó), monads phải được sử dụng để chỉ trạng thái luồng từ một phép tính sang tính toán tiếp theo. Bằng cách này, Haskell triển khai trình tạo số giả ngẫu nhiên của nó. Nói đúng ra, tạo ra các số ngẫu nhiên là một hoạt động vốn có của nhà nước, nhưng Haskell có thể che giấu thực tế này bằng cách di chuyển trạng thái "đột biến" thành hoạt động liên kết (>>=).

Điều này có vẻ hơi trừu tượng và nó thực sự không trả lời câu hỏi của bạn hoàn toàn, nhưng tôi nghĩ rằng nó vẫn có thể áp dụng được. Từ quan điểm lý thuyết, không thể làm việc với RNG mà không liên quan đến trạng thái. Bất kể, có những kỹ thuật có thể được sử dụng để giảm thiểu tương tác này và làm cho nó xuất hiện như thể toàn bộ hoạt động là bản chất không quốc tịch.

Answer 9

Máy phát số ngẫu nhiên, đúng [1], có thể thực hiện được, nhưng không tầm thường và thường có tỷ lệ trung bình thấp. Availablity cũng có thể là một vấn đề [2].Googling cho "tiếng ồn bắn" hoặc "phân rã phóng xạ" kết hợp với "trình tạo số ngẫu nhiên" sẽ trả lại một số lần truy cập.

Các hệ thống này không cần phải duy trì trạng thái. Có lẽ không phải những gì bạn đang tìm kiếm.

Như được lưu ý bởi những người khác, hệ thống phần mềm chỉ giả ngẫu nhiên và phải duy trì trạng thái.

Một thỏa hiệp là sử dụng RNG dựa trên phần cứng để cung cấp một nhóm entropy (trạng thái lưu trữ) được tạo sẵn để tạo hạt giống PRNG. Điều này được thực hiện khá rõ ràng trong việc thực thi linux/dev/random [3] và/dev/urandom [4].

Đây là một số đối số về cách ngẫu nhiên các đầu vào mặc định cho/dev/pool entropy ngẫu nhiên thực sự là.

---

Chú thích:

1. modulo bất kỳ vấn đề với sự hiểu biết của chúng ta về vật lý
2. bởi vì bạn đang chờ đợi một quá trình ngẫu nhiên
3. /dev/tính năng ngẫu nhiên truy cập trực tiếp đến hồ bơi entropy hạt từ nhiều nguồn khác nhau được cho là thực sự hoặc gần như ngẫu nhiên và chặn khi entropy cạn kiệt
4. /dev/urandom giống như/dev/random, nhưng khi entopy cạn kiệt một cryptog băm raphic được sử dụng làm cho hồ bơi entropy có hiệu quả một trạng thái PRNG

Answer 10

Việc sử dụng PRNG an toàn tùy thuộc vào ứng dụng của bạn. Các số ngẫu nhiên được sử dụng để làm gì? Nếu chúng có giá trị thực sự (ví dụ: bất kỳ thứ gì có liên quan mật mã), bạn sẽ không muốn sử dụng bất kỳ thứ gì ít hơn.

PRNG an toàn chậm hơn nhiều và có thể yêu cầu thư viện hoạt động chính xác tùy ý và kiểm tra nguyên gốc, v.v ...