TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

How do computers generate random numbers?

73 点作者 sunny--tech超过 3 年前

22 条评论

betwixthewires超过 3 年前
It&#x27;s a good introductory write up, but there are 3 things about it that frustrated me to no end.<p>&gt; &quot;As a human, I can do this very easily. 100101011010010110001101 There, I just did it.<p>No, you didn&#x27;t. That number is most certainly not random, there are biases in it, you just don&#x27;t know there are. Your mind is <i>not</i> random. This is why we use dice and not people to generate random bits.<p>&gt; What do you mean by “kind of random number”? Aren’t all random numbers the same. Not really. There are two primary types of random number generators.<p>I growled audibly at this one. <i>Random numbers should all be the same.</i> In quality, not quantity, of course. There should be no discernible difference. There is one kind of random number, only different types of <i>generators</i>, with a PRNG if the seed is provably destroyed there should be absolutely no way to distinguish between a number generated by a PRNG and a TRNG.<p>&gt; The computer hardware isn’t the only source of entropy. The user’s own mouse and keyboard movements can be used as well.<p>No. These movements are <i>not</i> random. Similar to my first gripe, your brain is not random. We used to use this approach to generate entropy and now we don&#x27;t because this is understood, &quot;random&quot; user inputs should absolutely never be used to generate randomness in anything security related.<p>&gt; Despite the benefits of CSPRNGs, as with everything else in the tech industry, security can never be guaranteed.<p>I&#x27;m glad you pointed this out. Everything in cryptography is based on unproven axioms, this is an important point that people should understand, it could be that P=NP, it could be that an algorithm exists to factor numbers to primes, we think not but really we don&#x27;t know.
评论 #28459401 未加载
评论 #28464182 未加载
评论 #28459929 未加载
评论 #28461324 未加载
评论 #28460148 未加载
评论 #28464981 未加载
评论 #28465299 未加载
评论 #28459261 未加载
xkeysc0re超过 3 年前
Writing your own random number generator can be a lot of fun. Lots of sources of entropy out there. Inspired by lavarand[0], I wrote an RNG in Python based on the output of the Global Conscousness Dot[1] (which is a ridiculous project in its own right). There&#x27;s a lot of ways to visualize and ascertain how &quot;random&quot; your numbers are as well, whether plotting Pearson&#x27;s with matplotlib or using a command line tool like ent[2] to calculate the degree of entropy.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lavarand" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lavarand</a><p>[1] <a href="https:&#x2F;&#x2F;gcpdot.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;gcpdot.com&#x2F;</a><p>[2] <a href="https:&#x2F;&#x2F;manpages.ubuntu.com&#x2F;manpages&#x2F;bionic&#x2F;man1&#x2F;ent.1.html" rel="nofollow">https:&#x2F;&#x2F;manpages.ubuntu.com&#x2F;manpages&#x2F;bionic&#x2F;man1&#x2F;ent.1.html</a>
评论 #28459515 未加载
评论 #28458815 未加载
评论 #28459579 未加载
Someone超过 3 年前
<i>“The most common algorithms used for PRNGs are linear congruential generators”</i><p>I doubt that is still true for ‘modern’ languages. Let’s google a few.<p><a href="https:&#x2F;&#x2F;docs.microsoft.com&#x2F;en-us&#x2F;dotnet&#x2F;api&#x2F;system.random?view=net-5.0" rel="nofollow">https:&#x2F;&#x2F;docs.microsoft.com&#x2F;en-us&#x2F;dotnet&#x2F;api&#x2F;system.random?vi...</a> says <i>“The current implementation of the Random class is based on a modified version of Donald E. Knuth&#x27;s subtractive random number generator algorithm”</i>. So, that’s a <i>no</i>.<p><a href="https:&#x2F;&#x2F;rust-random.github.io&#x2F;book&#x2F;guide-rngs.html" rel="nofollow">https:&#x2F;&#x2F;rust-random.github.io&#x2F;book&#x2F;guide-rngs.html</a> doesn’t appear to mention multiplicative algorithms, either.<p><a href="https:&#x2F;&#x2F;developer.apple.com&#x2F;documentation&#x2F;swift&#x2F;systemrandomnumbergenerator" rel="nofollow">https:&#x2F;&#x2F;developer.apple.com&#x2F;documentation&#x2F;swift&#x2F;systemrandom...</a> says <i>“SystemRandomNumberGenerator is automatically seeded, is safe to use in multiple threads, and uses a cryptographically secure algorithm whenever possible.”</i>
评论 #28471360 未加载
SavantIdiot超过 3 年前
I&#x27;ve been working with the NIST 800-22 evaluation suite [1] and yes, it is very hard. There are an infinite number of tests to determine if a number is random. Ultimately it comes down to probability that it is a good RNG&#x2F;PRNG and the application. Ironically, if a PRNG is good enough, it can often be BETTER than a random source (which is why RNGs have a conditioning phase).<p>[1] <a href="https:&#x2F;&#x2F;csrc.nist.gov&#x2F;Projects&#x2F;Random-Bit-Generation&#x2F;Documentation-and-Software&#x2F;Guide-to-the-Statistical-Tests" rel="nofollow">https:&#x2F;&#x2F;csrc.nist.gov&#x2F;Projects&#x2F;Random-Bit-Generation&#x2F;Documen...</a>
评论 #28459607 未加载
lscharen超过 3 年前
I&#x27;ll take this opportunity to link to Luc Devroye&#x27;s freely available book &quot;Non-Uniform Random Variate Generation&quot;.<p><a href="http:&#x2F;&#x2F;www.nrbook.com&#x2F;devroye&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.nrbook.com&#x2F;devroye&#x2F;</a><p>An undergraduate algorithms + statistics class is sufficient to get a lot out of this book, even if it&#x27;s just exposure to the wide variety of techniques for generating random numbers on a computer.
Borrible超过 3 年前
Use leftovers. They&#x27;re all over the Universe.<p><a href="https:&#x2F;&#x2F;www.researchgate.net&#x2F;publication&#x2F;283762433_The_Cosmic_Microwave_Background_Radiation_Power_Spectrum_as_a_Random_Bit_Generator_for_Symmetric_and_Asymmetric-Key_Cryptography" rel="nofollow">https:&#x2F;&#x2F;www.researchgate.net&#x2F;publication&#x2F;283762433_The_Cosmi...</a>
simonblack超过 3 年前
Two basic ways:<p>Computed:<p>NOT truly random. Way back in the late 70s, I had a BASIC program that used to output the very same set of 8-digit &#x27;random&#x27; numbers <i>every time the program was used</i>.<p>(Unless you did a special thing the first time, to obtain a random seed to generate a different sequence of pseudo-random numbers. IIRC, it was the number of machine cycles since the last time the floppy disk was accessed.)<p>Hardware:<p>Truly random: The machine counts machine cycles with a small maximum number before it overflows and restarts at zero. The machine looks at the time difference between things like key presses, or disk-spins, or something else that varies in time.<p>No matter how good you are the variation in time between your key-presses is never the same at the very small time-flow level. That number is used as a seed to a pseudo-random generator.
dragontamer超过 3 年前
A modern &quot;pseudo random number&quot; is simply a sequence of numbers that visits the state-space in an order that&#x27;s difficult to detect with modern statistical tests. (Chi-squared, among others). See PractRand or TestU01 as two packages for testing these sequences. That is to say: instead of the sequence &quot;0, 1, 2, 3, 4, 5... 4294967296... 0&quot;, your RNG will do some other sequence.<p>Yes, &quot;0, 3, 6, 9... 4294967295, 2, 5, 8... 4294967294, 1, 4, 7... 4294967293, 0, 3...&quot; is a RNG of sorts, but an example of a really, really bad one that would instantly fail most statistical tests. :-) But conceptually, the Mersenne Twister, LCGRNG, and LSFR all accomplish this. Its a &quot;reordering&quot; of the sequence. That&#x27;s it.<p>A &quot;cryptographic random number&quot; just adds a few additional tests to the pool of statistical tests. In particular: differential cryptography gets into the nitty gritty about which bits can predict the results of other bits. You have to assume that the &quot;opponent&quot; is willing to use extraordinary amounts of computing power to detect patterns.<p>If bit#25 has a 51% correlation with bit#30, you fail cryptographic random numbers. You need to be within 2^128 (at least) worth of security or more. That means a near 50% correlation (maybe 50.00000000001% is fine) between bits and future bits.<p>For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. If the &quot;opponent&quot; doesn&#x27;t know the key, the bitwise correlations are cryptographically sound (thanks to the hard work of the engineers behind AES).<p>A true random number generator is just a cryptographic number generator applied to a truly random seed. White noise generators are a well known electronic-engineer trick: resistor noise is everywhere but is rather small (but you can build a white-noise generator from Johnson Nyquist noise if you really wanted). More likely, you use shot-noise from a transistor junction, at least at the hobbyist level.<p>Intel &#x2F; AMD have true random number generators from some kind of electrical noise generator on every CPU, which feeds into cryptographic random number generators.<p>There are other sources of noise: radiation is a well known one but I&#x27;m not sure if they&#x27;re practical.<p>There&#x27;s a &quot;speed limit&quot; to white noise generators. You only can extract so much entropy from them in a given time (ex: Remember: CPUs operate at 4GHz, or 0.25 nanoseconds per clock tick). Cryptographic random number generators &quot;stretch&quot; the true seed of randomness, while the white-noise generator continues to grab more entropy.
评论 #28459152 未加载
评论 #28458865 未加载
rrauenza超过 3 年前
I&#x27;m trying to remember a technique based on listening to static or whitenoise and taking the least significant bit. You then take that stream of bits and postprocess it by looking for bit changes and don&#x27;t use them directly.<p>That&#x27;s a vague and I&#x27;m sure inaccurate description, but it isn&#x27;t enough for me to google it ... anyone know what I&#x27;m referring to?
评论 #28460209 未加载
mjreacher超过 3 年前
&quot;Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.&quot;<p>- John von Neumann
hdivider超过 3 年前
PCIe and USB cards like this are available, generating TRNs using quantum optics:<p><a href="https:&#x2F;&#x2F;www.idquantique.com&#x2F;random-number-generation&#x2F;products&#x2F;quantis-random-number-generator&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.idquantique.com&#x2F;random-number-generation&#x2F;product...</a>
anotherevan超过 3 年前
“The generation of random numbers is too important to be left to chance.” — Robert R. Coveyou
qq4超过 3 年前
I always wanted a Geiger counter for experiments like this.
评论 #28460565 未加载
kerblang超过 3 年前
Did we ever resolve the flame war over &#x2F;dev&#x2F;random vs &#x2F;dev&#x2F;urandom? I recall puzzling over endless threads of no-<i>you&#x27;re</i>-wrong
comeonseriously超过 3 年前
Back in the day, IIRC, you could set a sound blaster to generate white noise, then use that as either random number or input to your RNG algo.
dunefox超过 3 年前
I was asked to implement a random number generator in an interview not too long ago. This article should help...
评论 #28472591 未加载
评论 #28469081 未加载
jason_s超过 3 年前
I lost interest at &quot;The most common algorithms used for PRNGs are linear congruential generators.&quot;
fnord77超过 3 年前
I thought this was a solved problem for at least a decade with CPU instructions like `RDRAND`
评论 #28458873 未加载
sunny--tech超过 3 年前
Link to bypass paywall: <a href="https:&#x2F;&#x2F;betterprogramming.pub&#x2F;generating-random-numbers-is-a-lot-harder-than-you-think-b121c3e75d08?source=friends_link&amp;sk=508f781bd2b7e0fc279950284c5a49ae" rel="nofollow">https:&#x2F;&#x2F;betterprogramming.pub&#x2F;generating-random-numbers-is-a...</a>
评论 #28460374 未加载
abnry超过 3 年前
Obligatory XKCD: <a href="https:&#x2F;&#x2F;xkcd.com&#x2F;221&#x2F;" rel="nofollow">https:&#x2F;&#x2F;xkcd.com&#x2F;221&#x2F;</a><p>And also Dilbert: <a href="https:&#x2F;&#x2F;dilbert.com&#x2F;search_results?terms=Random+Number+Generator" rel="nofollow">https:&#x2F;&#x2F;dilbert.com&#x2F;search_results?terms=Random+Number+Gener...</a>
dekken_超过 3 年前
some might say, it&#x27;s impossible.
chipuni超过 3 年前
I just use the XKCD random number generator:<p><a href="https:&#x2F;&#x2F;xkcd.com&#x2F;221&#x2F;" rel="nofollow">https:&#x2F;&#x2F;xkcd.com&#x2F;221&#x2F;</a>