11
$\begingroup$

In thermodynamics, entropy is defined for gases. Of course, my laptop is not a gas. However, it contains a random number generator and I have seen the word ‘entropy’ being used in this context. Is this the same entropy? How can this entropy be linked to the definitions from thermodynamics?

UPDATE

I think my question is different from this question. That question is about information content, for example a book. However, this question is about the entropy of a random number generator. Those seem to be different because the contents of a book are fixed while the output of a random number generator is not yet fixed.

$\endgroup$
10

7 Answers 7

22
$\begingroup$

There are several definitions of entropy in physics, based on the work of Claussius, Gibbs, Boltzmann, and others. Of particular interest here is Boltzmann's definition, which relates entropy to (the log of) the number of equivalent "microstates" for a given system state. Boltzmann used the equation $S = k_B\ln \Omega$, where $\Omega$ is the number of possible microstates. in the system. Gibbs developed this further to come up with the equation $S = -k_B\sum_i p_i \ln(p_i)$, where $p_i$ is the probability that the system will be in microstate $i$.

In computer science, Claude Shannon was working in the 1940's on on quantifying the amount of "information" available in symbols in a sequence. He eventually worked out that for a random variable $X$, the amount of information received from that random variable was given by the formula $H(X) = -\sum_{x\in X}p(x)\log p(x)$, where $p(x)$ is the probability that the random variable will give $x$.

The two formulas I gave above are: $S = -k_B\sum_i p_i\ln p_i$ and $H(X) = -\sum_x p(x)\log p(x)$. With the exception of the constant multiplier and the choice of logarithmic base, both these formulas are essentially the same. ruakh points out in the comments that a change of logarithmic base is the same as multiplying by a constant. With that in mind, both equations can be simplified to $S \propto -\sum_i p_i\log p_i$ and $H \propto -\sum_x p_x\log p_x$, which differ only in the choice of dummy summation variable.

Both Gibbs Entropy and "Shannon Entropy" are similarly defined, and serve similar purposes in their respective fields. The smaller the entropy of a system, the easier it is to predict what microstate it is in, regardless of if you are talking about a box of gas or a stream of text over a wire.

Because entropy is a measure (in both statistical dynamics and information science) of the (theoretical) unpredictability of a system, it gets talked about in the context of random number generators because you want random number generators to be unpredictable, to have "high entropy". A pseudo-random number generator will have internal variables that can have a collectively high number of states. Generating a random number both gives you the number, but also modifies those internal variables in a deterministic way. But only a fraction of the possible states would give you the random number you generated, so there are only a fraction of the total number of states that the RNG could be in after generating that number. The entropy of the RNG has reduced. In theory, after extracting enough random variables, the RNG becomes completely predictable; there is only one state it could possibly be in. It has no entropy.

$\endgroup$
2
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ Oct 19, 2022 at 13:06
  • $\begingroup$ Re: "With the exception of the constant multiplier and the choice of logarithmic base": Note that, due to properties of logarithms, the choice of logarithmic base is a constant multiplier: $\log_b(a) = \log_c(a)/\log_c(b)$ for any a, b, and c, so if one definition uses base $b$ and one uses base $c$ then the results differ by the constant factor $\log_c(b)$. $\endgroup$
    – ruakh
    Oct 20, 2022 at 22:19
14
$\begingroup$

In thermodynamics, entropy is defined for gases.

In thermodynamics, entropy is defined for a state of knowledge about the microscopic particle configurations in a system—the positions, velocities, etc., of every particle in the system—also called microstates, consistent with macroscopic averages of the system like its temperature, pressure, etc., or macrostate.

The Gibbs entropy of a thermodynamic system in some known macrostate is defined to be $$-k_B \sum_s P(s) \log P(s),$$ where $s$ ranges over all possible discrete microstates, and $P(s)$ is the probability that a system with the known macroscopic temperature, pressure, etc., is in the specific particle configuration of $s$. In other words, $P$ represents our state of knowledge about the unknown microstate of the particle configuration, and the Gibbs entropy is a measure of uncertainty about what the microstate could be, knowing what the macrostate is.

Strictly speaking, the Gibbs entropy is defined for a probability distribution $P$ on microstates; at equilibrium with a set of macroscopic averages like temperature, pressure, etc., the thermodynamic entropy is the maximum of the Gibbs entropy over all probability distributions having those macroscopic averages. And, of course, the space of microstates isn't really discrete (except in some sense at the quantum level)—either you treat this as an approximation, or you take the limit as an arbitrary choice of discretization gets finer, or, instead of summing over discrete microstates, you integrate over phase space volume elements.

History: Clausius originally introduced the idea of entropy purely in terms of macroscopic heat transfer, without the microscopic perspective. Boltzmann connected entropy to the microscopic perspective of particle configurations in statistical mechanics, giving rise to the Boltzman entropy $k_B \log \Omega$, where $\Omega$ is the number—or, really, phase space volume—of possible microstates, assuming all are equiprobable. Gibbs generalized Boltzmann's formula to nonuniform distributions—Boltzmann entropy is just the special case where $P(s) = 1/\Omega$.

In information theory, we strip away the details of particle configurations—positions, velocities, etc.—and macroscopic averages—temperature, pressure, etc.—and generalize this to Shannon entropy, measuring a state of knowledge in any probability distribution supported on any domain:* $$-\sum_x P(x) \log P(x).$$ The base of the logarithm isn't important except to make entropy of two different probability distributions commensurate; in physics traditionally it is the natural log (or base $e^{1/k_B}$ in a sense), and in information theory and cryptography traditionally it is base 2 in which case we talk about entropy in units of bits.

Claude Shannon devised this notion of entropy as a general measure of uncertainty, with applications to compression and cryptanalysis, and with the property the entropy of two independent unknowns is the sum of their respective entropies—this will come in handy for cryptography.


Cryptography is the design and study of games that an adversary can play, in the sense of game theory, with guarantees on how high the adversary's success probability is even when the adversary knows how the game works and everything in it and the other players' strategies except for small secret keys known only to the other players. "Success" here means, for example, guessing a secret bit in an encrypted message sent by a player, or forging a signature on a message and fooling a player into accepting it.

How do the players in cryptography choose their keys? They could flip coins, roll dice, count ionizing events in a Geiger–Müller tube or use the events to sample a clock, or—more practical in mass-manufactured silicon computers—sample bits with stochastic circuits like drifting independent ring oscillators or metastable flip-flops affected by thermal noise (arising from unknown microscopic particle configurations in the thermodynamic system of the silicon die!). An understanding of the physics behind these systems—and a crucial assumption that the adversary can't see the players' observations of these systems—tells us the entropy, in the adversary's state of knowledge, of the outcomes of observing them. The component—whatever it is under the hood—for generating secret keys in cryptography is a random number generator.

[My laptop] contains a random number generator and I have seen the word ‘entropy’ being used in this context. Is this the same entropy?

Cryptography is actually usually concerned with a different but related notion of entropy: min-entropy, $$-\max_k \log P(k),$$ where $k$ ranges over all possible keys, because cryptography is all about making sure the adversary's largest success probability using the best strategy is still small. (In contrast, in, e.g., compression algorithms, without an adversary, we care more about the average compressed message length, not just about the most probable message, so compression is usually concerned with Shannon entropy.) Min-entropy and Shannon entropy are both instances of the Rényi entropy family, $$H_\alpha := \frac{1}{1 - \alpha} \log \sum_x P(x)^\alpha,$$ with Shannon entropy being the limit as $\alpha \to 1$ and min-entropy being the limit as $\alpha \to \infty$. Min-entropy and Shannon entropy are related by theorems like the leftover hash lemma used in cryptography.

For practical and numerological reasons—based on thermodynamic limits on the adversary's energy budget!—we typically require the keys to have min-entropy of at least 128 or 256 bits, meaning that the adversary's probability of guessing them is at most $1/2^{128}$ or $1/2^{256}$.† If consecutive samples of a physical system like coin tosses, die rolls, G–M-driven clock samples, etc., are independent (or mostly independent), we can keep taking more of them to get enough entropy for cryptography, because entropy of independent unknowns sums, and we can compress large collections of samples into small keys with a hash function.

And, for simplicity of design and of proving theorems in cryptography, we usually require keys to be uniformly distributed, in which case the min-entropy and Shannon entropy coincide—we get uniformly distributed keys from physical observations like clock samples by feeding the observations through hash functions, called conditioning components, to smooth out the distribution.


But how much entropy do we need for cryptography, you might ask?

In a cryptographic game, the players will do things like encrypt messages into ciphertexts or sign messages giving signatures which are then exposed to the adversary, revealing to the adversary deterministic functions of their secret keys like $\operatorname{SHA256}(k)$ or $\operatorname{AES}_k(123)$ or $m^3 \bmod p\cdot q$ for secret $k$, $m$, $p$, and $q$.

In principle, deterministic functions of a random variable cannot have higher entropy than the random variable itself. So in theoretical terms, knowledge of $\operatorname{AES}_k(123)$ can narrow down $k$ to a small set of candidate 256-bit strings, meaning the conditional entropy of $k$ given $\operatorname{AES}_k(123)$ is much lower than 256 bits.

However, these functions are chosen to be one-way, that is, chosen to be difficult to invert: we don't know any algorithm that will find, with the energy resources humanity can expend, a single candidate 256-bit string $k$ given only the value of $\operatorname{AES}_k(123)$ and the knowledge that every possible key has probability $1/2^{256}$—or even given the values of $\operatorname{AES}_k(123),$ $\operatorname{AES}_k(124),$ $\dotsc,$ $\operatorname{AES}_k(n)$ for very large $n$.

Protocols like TLS are designed with theorems saying that:

  • if an adversary can attain better success probability than so and so with such and such cost at breaking the security—guessing an unknown bit in a message, forging a message, etc.
  • then the adversary must have found a cheaper way to invert AES than a generic search (or the other players' secrets must have been leaked, e.g. via a side channel attack).

The result of these theorems—and of the decades of failure by clever cryptanalysts to find any techniques for inverting AES—is that cryptography really only requires a small amount of min-entropy for users, and can then simulate generating fresh observations with more min-entropy by using deterministic algorithms called pseudorandom number generators or deterministic random bit generators like AES-CTR_DRBG. As far as the adversary is concerned, these "observations" might as well have been chosen by flipping coins, not by a deterministic algorithm—as long as the players keep their keys secret.

But you still need those first 256 bits of entropy, which is why your laptop most likely has a stochastic circuit wired up through an AES circuit as a conditioning function to a CPU instruction called RDRAND (or RNDRRS or DARN or …) used to kick off cryptography so you can log into stackexchange.com without anyone being able to impersonate you over the network.


* Any discrete domain, that is. With a lot more mathematical chicanery this can also be generalized to continuous domains, using probability densities and Lebesgue integrals and a lot of nonsense invented principally to torment graduate students in mandatory classes and quals on measure theory.

† Some commentators suggest that Kolmogorov complexity, sometimes called "Kolmogorov entropy", is relevant to random number generators. But it is not. The Kolmogorov complexity of a string is always defined relative to a language, and it means: What is the length of the shortest program in this language that can produce the string as output? For example, the Kolmogorov complexity of the first 1000 decimal digits of $\pi$ in FORTRAN 77 is the number of bits in the shortest FORTRAN 77 program (without libraries) that will print the first 1000 decimal digits of $\pi$. This depends fundamentally on the choice of language; the Kolmogorov complexity of the first 1000 decimal digits of $\pi$ in Python 2.7 is likely to be very different from its Kolmogorov complexity in FORTRAN 77. This has nothing to do with quantifying an adversary's uncertainty about secrets, and everything to do with code golfing, and thus figures only into very obscure corners of cryptography.

$\endgroup$
7
  • 2
    $\begingroup$ Nice answer, seems like the first one to really take on the difference / similarity between information-theoretic entropy and physical thermodynamic entropy. rdrand in Intel CPUs is said to re-seed a CSPRNG from true hardware randomness quite frequently. The whitening process involves AES, but unless the CPUs work differently from what's been published, there is fresh entropy coming in continuously, not just 256 bits ever! electronicdesign.com/resources/article/21796238/… $\endgroup$ Oct 19, 2022 at 12:59
  • $\begingroup$ Yes, RDRAND does continuously sample, but in a cryptographic protocol you only need 256 bits of entropy to start. This is why, for instance, some modern operating systems will hold up starting networked programs until they've gathered around 256 bits of entropy, and then never hang again waiting for entropy—programs requesting more will be served by a PRNG keyed by a hash of the samples taken so far without ever needing to wait for more. $\endgroup$ Oct 19, 2022 at 13:01
  • $\begingroup$ Oh, I see what you're saying now, you aren't saying that rdrand is just a CSPRNG, you're suggesting an implementation mechanism (sampling low bits of a fast clock at times not synced with it) different from the published one (metastable flip-flop state decaying to 0 or 1 from thermal noise, as described in the link in my first comment). Yes, agreed, usually you'd use rdseed (or /dev/urandom which might mix it in) to seed a CSPRNG, that's what it's for. $\endgroup$ Oct 19, 2022 at 13:04
  • 1
    $\begingroup$ You're right, sorry—it is a different design. AMD allegedly uses a collection of independent ring oscillators to get samples affected by jitter, and Intel formerly used a similar design prior to RDRAND, presumably on the 82802AB/82802AC firmware hub $\endgroup$ Oct 19, 2022 at 13:41
  • 1
    $\begingroup$ …but you're right, Intel's alleged RDRAND design is different and affected directly by the thermal noise in the silicon, not indirectly via clock jitter. $\endgroup$ Oct 19, 2022 at 13:42
14
$\begingroup$

Are you asking if running an algorithm on your laptop generates entropy? Yes, it does. It is an irreversible process. The electronics requires electrical energy and converts it into heat. Is that the minimal entropy generation of the algorithm? No. It's many orders of magnitude more than that with current technology. However, there is a fundamental limit to the power requirements of computers and it is given by the energy needed to "flip a bit" in the computer's memory. Since a bit can only hold information if the threshold energy for a flip is several times kT (otherwise it will flip randomly due to thermal noise), every time we perform such a change of memory content we have to expend that much energy and that energy becomes heat.

$\endgroup$
2
  • 12
    $\begingroup$ This answer would be improved by addressing why the concept of "entropy" arises in random number generators, not just the heat generated by any computation of an algorithm. $\endgroup$ Oct 19, 2022 at 15:52
  • 1
    $\begingroup$ @FlawedShannon Agreed. Let me think about it. I am happy to make changes. If you want, you are very welcome to make an edit that you deem useful. Initially I was thinking about writing something about reversible computation since I believe it ties into the theme. $\endgroup$ Oct 19, 2022 at 19:56
4
$\begingroup$

I'm not sure the existing answers really address what I understand to be your question. In general, you can think of entropy as a measure of how lossy a map from microstates to macrostates is. The microstate is the exact state of your system and the macrostate is some "coarse-grained" picture of the system. Entropy is not a single thing; it is only defined relative to some choice of microstates and macrostates. Technically speaking, when invoking the concept of entropy, one should specify what the microstates and macrostates in question are. In practice though, this is often left to context.

For example, if I'm talking about a gas, it is implicit that the microstates are the exact positions and velocities of the particles and that the macrostates are things like the temperature, pressure, etc. In the context of a random bit (like your random number generator might output), the microstates are understood to be 0 and 1 and there is simply a single macrostate. The entropy in either context is a measure of how much information of the microstate is missing when only the macrostate is known.

A definition of entropy is most meaningful when the macrostates are chosen to be the things you do know/can measure. There's usually some natural choice. The usefulness of the usual definition of the thermodynamic entropy of a gas is based on our natural inability to keep track of the exact motion of a large number of very small particles together with our ability to directly experience/measure things like temperature and pressure. By contrast, a being that could keep track of the motion of many small particles, like Maxwell's demon, might not find this notion of entropy very meaningful.

$\endgroup$
7
  • 2
    $\begingroup$ +1. The crucial point many people, i.e. physicists, miss is that entropy depends on the choice of macro states (and or micro states as well). This makes entropy "anthropomorphic" or "subjective" or "contextual". $\endgroup$ Oct 19, 2022 at 8:07
  • $\begingroup$ @TobiasFünke Entropy to a physicist is always dS=deltaQ_rev/T or dS>=dQ/T. There is nothing "anthropomorphic" or even contextual about (ir)reversible heat transfer as far as I can tell. $\endgroup$ Oct 19, 2022 at 12:43
  • 5
    $\begingroup$ @FlatterMann We had this discussion some weeks ago. You've already proven that you don't understand the information theoretic approach (but even in "classical" thermodynamics/ statistical mechanics this is the case, as the different macro variables define different entropy functions, and to one physical system one can associate different thermodynamic systems and thus entropies, roughly speaking). $\endgroup$ Oct 19, 2022 at 12:44
  • $\begingroup$ @TobiasFünke We can have a discussion about why reusing the word "entropy" was a bad idea, if you like. Thermodynamic systems have a temperature (at least on the edges) and heat only moves from hot to cold without anything else happening. These are facts. I don't know why this seems to have become such a big deal to people who like to think about "information". Be that as it may, peace. $\endgroup$ Oct 19, 2022 at 12:54
  • 4
    $\begingroup$ @FlatterMann Again: If you'd understand it, you'd know that the approach resembles equilibrium thermodynamics. I really don't know what you want, every time, with temperature and so on. I've (and anybody else using the IT approach) never claimed that thermodynamics is wrong or anything. $\endgroup$ Oct 19, 2022 at 13:00
3
$\begingroup$

Your laptop likely has a real hardware-based random number generator. Common implementations use electrical noise, caused by the fact that your hardware exists at a temperature above 0K.

However, the entropy of that electrical noise is reduced by many, many orders of magnitude. To name just one simple statistical reason: the electrical noise won't have a uniform distribution, but the random-number generator in your computer should be. There are techniques to mitigate this, so-called whitening, but these lose entropy in the process. Also, the random number generator should be safe for cryptographic processes, which requires additional steps that lose entropy.

See https://stackoverflow.com/a/27326791/15416 for a description of the RDRAND instruction that's likely in your laptop. The entropy there is quoted at 626,176 bits of entropy, or about $6*10^-18 J/K$.

$\endgroup$
1
  • $\begingroup$ That 626,176 bits is for a specific benchmark that ran rdrand 10000000 times, assuming worst-case reseeding frequency of the CSPRNG that's used to whiten the entropy. electronicdesign.com/resources/article/21796238/… . (And assuming no exhaustion of the buffer rdrand pulls from, since they didn't check the bool result). If you don't run rdrand or rdseed often, you can pretty much assume you get a full 32 or 64 bits of entropy from each one. (And reportedly, 16 or 32-bit rdrand still pulls 64 bits from the pool.) $\endgroup$ Oct 19, 2022 at 10:28
1
$\begingroup$

The answer is simply that a random number generator's entropy and Thermodynamic entropy are not the same things.

A couple of distinct features of thermodynamic entropy is the following.

  • Every thermodynamic entropy depends on a variable corresponding to the thermodynamic energy of the system.
  • Thermodynamic entropies are defined for equilibrium states of macroscopic systems.

In the absence of these two conditions, whatever concept we give the name of entropy will be useless as a thermodynamic quantity. Said in another way, non-thermodynamic entropies are entirely decoupled from thermodynamics.

Nothing prevents us from associating the name of entropy with one or more concepts connected to random number generators (RNG). For instance, we can associate an RNG with Shannon's or Kolmogoroff's entropies (conceptually different entropies). However, no established or reasonable concept of equilibrium can be associated with RNGs, and there is no energy they depend on. We could say that we have a composite system consisting of the material the computer is made of and the RNG, and that the total entropy is the sum of the thermodynamic entropy of the hardware plus Kolmogoroff's (or Shannon's) entropy of RNG. However, that's all. There is no way to speak about a redistribution of energy maximizing the total entropy.

Notice that the decoupling between different entropies does not mean that the common features of the two definitions can't help shed light on the concept itself.

$\endgroup$
6
  • $\begingroup$ If you define the entropy of the composite system as thermodynamic entropy plus Kolmogoroff’s entropy, is it then still impossible for the total entropy to decrease? $\endgroup$
    – Riemann
    Oct 20, 2022 at 7:44
  • 1
    $\begingroup$ @Riemann There is no way to make those two "entropies" communicate. The sum of both will remain forever that value. This is at variance with the situation of a composite system made by two thermodynamic subsystems that may exchange energy. $\endgroup$ Oct 20, 2022 at 8:03
  • $\begingroup$ In the Maxwell’s Demon situation, thermodynamic entropy can be converted to information entropy, so why can’t we convert it to the entropy for a random number generator? $\endgroup$
    – Riemann
    Oct 20, 2022 at 8:07
  • 1
    $\begingroup$ @Riemann in Maxwell's Demon situation, information entropy is directly connected to information about the molecules of the gas. I.e., the system is a thermodynamic system. This is not the case with random numbers. $\endgroup$ Oct 20, 2022 at 8:21
  • 1
    $\begingroup$ @Riemann There is no mention in the question that one should limit the discussion to RNG based on the random noise of electric circuits. But even in such a case, the same physical system (the random noise) could be used to generate random numbers or a constant sequence. What would be the relation between the number sequence's entropy and the thermodynamic physical source's entropy? Are you able to provide a formal connection between them, apart from using the same name (entropy) for both? Where is energy in the sequence of random numbers? $\endgroup$ Oct 20, 2022 at 11:27
-3
$\begingroup$

I am not sure about my expertise. But here is a shot anyway.

The 'random number generator' will keep giving numbers out. And it never ends. So it keeps drawing energy out from your computer. And I doubt you can covert the heat created back to energy which would power your computer.

Of course the random-number-generator may be applied to solving problems in mathematics, physics which in turn will generate energy back.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for the attempt. However, answers on Stack Exchange sites are expected to answer the question; see tour and How to Answer for details. You're right to doubt that the heat can be converted back to energy; this is basically the concept of thermodynamic entropy! But in the physics sense, solving physics problems doesn't "generate energy". Your lack of expertise is showing; your answer has less answer in it than the question. (Don't let this discourage you; your intuition looks good, and expertise only comes from study, practice and experience. Unless you're a pure mathematician.) $\endgroup$
    – wizzwizz4
    Oct 18, 2022 at 15:44
  • $\begingroup$ Dear wizzwizz4, can you post the correct answer so that I can rectify my understanding. Thank You. $\endgroup$ Oct 19, 2022 at 6:16
  • $\begingroup$ physics.stackexchange.com/a/732558/105169 is a good, simple answer, but skips some of the question. physics.stackexchange.com/a/732653/105169 is more detailed, but a bit harder to understand (and there are a couple of things the first answer says that the second doesn't). $\endgroup$
    – wizzwizz4
    Oct 19, 2022 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.