Path: csiph.com!eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: bartekltg Newsgroups: comp.programming Subject: Re: Researches in quantum computing seem to progress only extremely slowly Date: Thu, 03 Sep 2015 02:51:34 +0200 Organization: Aioe.org NNTP Server Lines: 106 Message-ID: References: <20150901072207.925@kylheku.com> <20150901111251.317@kylheku.com> <20150902054403.661@kylheku.com> NNTP-Posting-Host: 8yDXz2POMePMu60eIS0/Vw.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.8.0 X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:5766 On 03.09.2015 02:22, Mok-Kong Shen wrote: > Am 03.09.2015 um 02:01 schrieb bartekltg: >> On 03.09.2015 01:28, Mok-Kong Shen wrote: >>> Am 03.09.2015 um 01:21 schrieb bartekltg: >> >>>> >>>> >>>> This is exactly the answer to you question about 'mean entropy'. >>>> You did not understand the direct answer because you do not >>>> know math about entropy. This is why I also wrote the second >>>> post about simplified problem, but with the same question >>>> and answer. >>>> >>>> If I have a candy in one hand I do not have a half of bits >>>> of enthropy in each hand. I have one bit in left and one >>>> bit in right. But both bits are corelated, so if you >>>> known one, you also known the second - second hand >>>> have zero entropy, because ("under the assuption the >>>> first hand in known") you known where the candy is. >>>> >>>> "Mean entropy" as you proposed ("128/n") have no sense, >>>> because probability doesn't work that way. >>> >>> Ok, then simply entropy. Lets say that the 128 input bits >>> are all of full entropy, each bit has entropy of 1.0. We >>> assume that AES is very well designed such that the output >>> n bits are equally good. How much entropy has under this >>> assumption one output bit? >> >> One bit. >> If AES is good, both 0 and 1 is equally probable, >> so entropy is >> -1/2*log(1/2) -1/2*log(1/2) = 1 >> >> >> Entropy of two bits is almost two. >> >> Entropy of the whole n bits is not greater than 128bits >> //forth dot >> https://en.wikipedia.org/wiki/Entropy_(information_theory)#Further_properties >> > > So, assuming that the n bits are equally good, the entropy > of each output bit is not greater than 128/n. A trivial > calculation, isn't it? No. You still don't get this hands and a candy story ;] We have two bit random sequence. 00, 01, 10, 11, all with probability 1/4. AES_2_4 generate: AES(00) = 1011 AES(01) = 1000 AES(10) = 0111 AES(11) = 0110 [you can write better "AES" bunction and recalculate entropies] Do you know definition of entropy? x_i are possible sequewnces. P(x_i) propability od that seqence. entropy H = \sum_i P(x_i)*log2(1/P(x_i)) Entropy of first bit is 1 Entropy of second bit is 1 entropy of third bit is 1/4log2(4) + 3/4log2(4/3) = 0.81128 entropy of fourth bit is 1 Entropy of first two bits? We have only two possible sequences. 01 and 10. Both have probability 1/2. So H = 1 First two bits have only one bit of entropy. -How, first bit have one bit, and second bit have one bit, this is total two bits! look at the sequences. If I look at first bit and it is 1, i know random sequieince was eithier 00 or 01. But if I look at the second bit, I will not get any new information, i knew before tjat second bit is NOT first bit. First bit carry information, second bit carry information, but this is the same information. Second and third bit can be: 00, 01, 11. The last with propability 1/2, first two - 1/4. H = 1.3466 The first and the last bit: sequences: 11 10 01 00. propability od any =1/4. H=2. If I look at these two bits, I can decipher whole sequence. They carry whole information. If I know that, the rest of the sequence have no more information for me. Entropy of whole sequence is... of course 2 bits, beceuse i have 4 possible sequences, echch with 1/4 chance. bartekltg