Messages in this thread | | | Date | Fri, 15 Aug 2003 10:11:16 -0500 | From | Matt Mackall <> | Subject | Re: [RFC][PATCH] Make cryptoapi non-optional? |
| |
On Fri, Aug 15, 2003 at 10:06:42AM +0200, M?ns Rullg?rd wrote: > Andries Brouwer <aebr@win.tue.nl> writes: > > >> > > entropy(x) >= entropy(x xor y) > >> > > entropy(y) >= entropy(x xor y) > >> > > >> > Is this trolling? Are you serious? > >> > >> These lemma are absolutely true. > > > > David, did you read this line: > > > >> > Try to put z = x xor y and apply your insight to the strings x and z. > > > > Let us do it. Let z be an abbreviation for x xor y. > > > > The lemma that you believe in, applied to x and z, says > > > > entropy(x) >= entropy(x xor z) > > entropy(z) >= entropy(x xor z) > > > > But x xor z equals y, so you believe for arbitrary strings x and y that > > > > entropy(x) >= entropy(y) > > entropy(x xor y) >= entropy(y). > > > > This "lemma", formulated in this generality, is just plain nonsense. > > Not quite non-sense, but it would mean that for any strings x and y, > > entropy(x) == entropy(y), > > which seems incorrect.
No, it's a premise stated at the beginning of the thread. We're assuming perfect distribution for x and y. The problem here is that x and y can be dependent or independent. If they're independent, then there's no issue. If they're dependent (for instance correlated or anticorrelated) then x^y biases toward zero or one. Which clearly has less entropy.
-- Matt Mackall : http://www.selenic.com : of or relating to the moon - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |