4 ms·
Linear Congruential Generators
- templeos2 12y agoI use the 14Mhz HPET for a random number for each word with keypress. I can use 5 different quantum random websites. NIST random beacon. ------------------ NIST Randomness Beacon Summary: NIST is implementing a prototype source of public randomness. The prototype (at https://beacon.nist.gov/home https://beacon.nist.gov/home) uses two independent commercially available sources of randomness, each with an independent hardware entropy source and SP 800-90-approved components. The Beacon is designed to provide unpredictability, autonomy, and consistency. Unpredictability means that users cannot algorithmically predict bits before they are made available by the source. Autonomy means that the source is resistant to attempts by outside parties to alter the distribution of the random bits. Consistency means that a set of users can access the source in such a way that they are confident that they all receive the same random string. Description: The Beacon will broadcast full-entropy bit-strings in blocks of 512 bits every 60 seconds. Each such value is time-stamped and signed, and includes the hash of the previous value to chain the sequence of values together. This prevents all, even the source, from retroactively changing an output packet without being detected. The beacon keeps all output packets and makes them available online. DRBG Beacon System Diagram Uses: Tables of random numbers have probably been used for multiple purposes at least since the Industrial Revolution. The first published table appears to be by the English statistician L.H.C. Tippett. In the digital age, algorithmic random number generators have largely replaced these tables. The NIST Randomness Beacon expands the use of randomness to multiple scenarios in which the latter methods cannot be used. The extra functionalities stem mainly from three features. First, the Beacon-generated numbers cannot be predicted before they are published. Second, the public, time-bound, and authenticated nature of the Beacon allows a user application to prove to anybody that it used truly random numbers not known before a certain point in time. Third, this proof can be presented offline and at any point in the future. For example, the proof could be mailed to a trusted third party, encrypted and signed by an application, only to be opened if needed and authorized. NIST encourages the community at large to research and publish novel ways in which this tool can be used. A few examples of applications are described below: Unpredictable Sampling New Secure Authentication Mechanisms Secure Multi-party Computation A Quantum Source: Commercially available physical sources of randomness are adequate as entropy sources for currently envisioned applications of the Beacon. However, demonstrably unpredictable values are not possible to obtain in any classical physical context. Given this fact, our team established a collaboration with NIST physicists from the Physical Measurement Laboratory (PML). The aim is to use quantum effects to generate a sequence of truly random values, guaranteed to be unpredictable, even if an attacker has access to the random source. In August 2012, this project was awarded a multi-year grant from NIST's Innovations in Measurement Science (IMS) Program. IMS awards highly competitive projects designed to explore high-risk, leading-edge research concepts that anticipate future measurement and standards needs of industry and science. For more information on this collaboration see http://www.nist.gov/pml/div684/random_numbers_bell_test.cfm http://www.nist.gov/pml/div684/random_numbers_bell_test.cfm Locality-Loophole-Free Bell Test A space-time diagram illustrating a locality-loophole-free Bell test. In this test, entangled photons are verified to have correlations that exceed the maximum level possible with any predetermined (or classical) states. To demonstrate this unequivocally, it is important to make sure that the measurements performed on one photon cannot, by any means within the bounds of physics, influence the measurement of the other photon. Such an influence, if it were to exist, could allow fully predetermined states to appear to share quantum correlations. Conducting the two measurements outside of each other's light cones ensures this measurement independence. In the space-time diagram above, the speed of light is depicted by rays at ±45 degrees, and also represents the maximum speed at which information about any event could (conceivably) propagate away from the origin of the event. Therefore, positions outside the cone formed by the rays from any event represent locations and times that could not possibly have received any information from the event. In the loophole-free test illustrated above, entangled photons are emitted from the source and propagate in opposite directions towards receivers Alice and Bob. At some point in time, indicated by "i" and "j," Alice and Bob each independently choose how to measure the properties of the photon each will receive. To conduct a locality-loophole-free Bell test, Alice and Bob must complete their chosen measurements (Ai,and Bj, determining results a and b, respectively.) before any information about the other's choice could possibly reach their location; Alice must complete her measurement before the rays emanating from the event "j" intersect her location, similarly Bob must complete his measurement outside the light cone of event "i." Closing this and other loopholes in the Bell test provide certification that no information about the state of the photons could have been available prior to its observation, assuring that the correlations could not have been predetermined. That guarantee of no predetermination of the photon system and its measurement results, will ultimately be used to produce random bits that can be assured to be both random and unknown to anyone before a certain time.
- sjolsen 12y ago> However, because the implementation of rand is unknown, it is impossible to tell whether or not using modulus to shrink the range will result in an acceptably random sequence. The reason that this might not be the case is due to the very definition of linear congruential generators. Using the modulus operation to transform the range of std::rand is problematic, but it isn't because of any attribute of the implementation of std::rand or of linear congruential generators. One problem with using modulus to scale a random distribution is that it fails to preserve uniformity. For example, consider a function 'rand150' whose result is uniformly distributed on [0, 150); that is, each number in the range [0, 150) has the same probability (1/150) of being returned by any given call to rand150. Now, if you use modulus to scale to [0, 100): x = rand150() % 100; there are 100 possible values for x. For any value greater than or equal to 50, there is exactly one result of rand150 which could produce that value; therefore, the probability of x being that value is 1/150. But for values less than 50, there are two results of rand150 which could produce that value, giving it a probability of 2/150. Since half of the possible values of x have a probability of 1/150 each and the other half have a probability of 2/150 each (you can check that this adds up to a probability of 1), the distribution is very much nonuniform. This result does not apply just to small ranges; it applies any time you scale down the range by anything but an integer multiple, although it approaches uniformity more closely the smaller the target range is compared to the source range. The other problem is that you can't make the range bigger. Well, you actually can— but some of your "x" values will have a probability of zero, which probably isn't what you want. Considering rand150 again, if you try to scale to [0, 300) by doing: x = rand150() % 300; how often do you expect to get 250? > The common solution is to use the constant value RAND_MAX, defined with every standard library, to use the high-order bits of a random number through division rather than low-order bits with the remainder of division I'm not sure if there's a typo in the code, but if RAND_MAX is, say, 200, then rand() / (RAND_MAX / 100 + 1) gives you values on [0, 66]. Probably not what you want. > An alternative to dividing RAND_MAX by N is to force the expression to floating-point and multiply RAND_MAX by N Mathematically, this would be a sensible way of scaling continuous uniform distributions, or at least it would be if floating-point numbers weren't so imprecise. When dealing with discrete distributions, though, this approach still has problems. For example, what if rand gives values on [0, 30) and I want values on [0, 20)? Let's see what values of rand map to, assuming perfect real numbers: rand x 0 floor(0) = 0 1 floor(2/3) = 0 2 floor(4/3) = 1 3 floor(6/3) = 2 4 floor(8/3) = 2 Unfortunately, 1 will only be generated half as often as 0 or 2. > Yet another alternative is to utilize the uniform_deviate function provided not too long ago Mathematically, this is equivalent to the above. The floating point arithmetic may be very slightly different, but it will make the result worse if anything.