On 1/12/10 9:39 AM, sascha wrote: >> The chain merging data is interesting. I see from the data below >> that the percentage of chains merged starts at 5% and then decreases >> linearly with the number of start values. The interesting thing is >> this: >> (vertical axis: % of chains lost, horizontal axis: chains left) >> screenshot of graph >> >> I clearly see two lines. It appears that round functions 10, 14, 17, >> 21, 24, 28 and 31 (+/- 1) generate 0.5% less chain mergers. Do we >> have any clue why? Do they share a common bit value, or have a >> certain number of bits? Could you reconstruct the xor patterns for >> the 32 rounds, Sacha? >> > > advance was 307232, second column is numbits==1 count > the only pattern i see is that the rounds with less chain mergers are > evenly spaced (ignoring round 1 - 10) > > The values seem pretty prng to me. Probably just random fluctuation with > some influence on the next few rounds which restore the balance again. > > hmm. no smoking gun indeed. 32 samples of 64 parameters are bound to give some pattern, so we should have some more data to collect statistics. If picking the right round mask saves us a few % chain mergers, we could increase table quality.
A few experimental requests if you would like to investigate this further: - redo with the same bitmasks to see if it's a fluctuation or if those bitmasks are indeed special (with 1024*1024*100 start values and only one round per bitmask we could see if the % mergers fits on one of the equations found, so that's 0.1 Ground per experiment) - redo with combinations of bitmasks. see if (good bitmask)^(good bitmask) == (bad bitmask), (good bitmask)|(good bitmask) == (better bitmask), (good bitmask)&(good bitmask) == (good bitmask) etc etc, same for s/good/bad/g So simply running a round over and over again with an array of precomputed bitmasks should give more insight. as for the numbers you provided, written as bits, counted per bit position and taking biggest differences between good/bad masks: (* denotes favourable bitmask) (left col = hex bitmask, right col = bits 60+52+44+31+11) 39894c217a0103d7 10000 e1ba888001e4d846 01001 cb4caa7fecb9d16e 00010 4c85f57e646611db 00100 86011c6836045ef7 00101 25e5fe857594042d 00100 e0a1e00c94a39038 00010 d10cdf47ad3ecdfd 10111 14419070b2a619c1 10111* 2528cbe0974487a7 00010 eb4c42d3885e3056 00010 2c8d032fa00f28d6 00011 26d0d1081f654d56 01101* cf051426d32e97de 00110 268920cf2111848e 00000 c8bf942585591ef6 01111* 683aa0e50f4dc430 01000 85cf17a8609bd122 00100 032700c2533017a9 00000 d1def48ea02e00d6 11110* 1e840ef31c1df554 10000 c0137443fae91fe8 01111 be66851b891dde08 10011* 280809b7bdea8d24 00011 472733e1083cd3f5 00100 7ddc0ac425912b1c 11001 4abb1ad0e4d76bfd 01111* de5bab07b94ba3ca 11010 8a74eab16ac4395c 01001 958b3eb1bad1eb37 10111* b588a2bb4b1c2861 10001 d5a9265ccbf8424e 10010 0, 1 or 2 bits set means bad bitmask. not a very strong case. There is the possibility that there are a number of different patterns which steer away from chain mergers. We will need more data to discover them. > >> (equations are: >> y = 4.5613 * 10-9 x + 0.1163 >> y = 3.937 * 10-9 x + 0.0581) >> >> And if you could find the time to do it, I would really like to see >> the same table but then for the 100-forward case. I hope to relate >> some real-world data to the statistics derived above. >> >> > > sure. some more debugging and 3 days to build the table. > i hope you do not mean exactly the same table, but the same layout, > different advance, different start values, cause then i would have > to find the seed that mersenne twistered the start values again ;) > > Of course, I only care about the statistics. Big N will do the rest. Would it be an idea to collect such statistics from table generation, where they are readily available? Simply tracking the xor pattern, # of chains total and % of chains merged will do the trick if we need some more data to analyse. Plotting the collected % merged against # total might reveal more lines in the plot. (or could we distill them from the tables we have already?) Kind regards, M. >> On 1/12/10 12:58 AM, sascha wrote: >> >>> For a 32 rounds table with 1024*1024*1024 start values: >>> 1 1073741823 >>> 2 1023438982 >>> 3 976087268 >>> 4 932768763 >>> 5 893795050 >>> 6 857258423 >>> 7 824594686 >>> 8 793842630 >>> 9 764984529 >>> 10 742264968 >>> 11 717542086 >>> 12 693794500 >>> 13 671348674 >>> 14 653519282 >>> 15 633911863 >>> 16 615705741 >>> 17 600811372 >>> 18 584022929 >>> 19 567966279 >>> 20 553038610 >>> 21 541126688 >>> 22 527714176 >>> 23 514813648 >>> 24 504121909 >>> 25 492442040 >>> 26 480922764 >>> 27 469931269 >>> 28 461146395 >>> 29 451036696 >>> 30 441442433 >>> 31 433670029 >>> 32 ? >>> 33 ? >>> >>> sum: 20.5 Grounds >>> (instead of 30 Grounds) >>> >>> > _______________________________________________ > A51 mailing list > [email protected] > http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 > > _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
