--- Day changed Sat Dec 05 2015
00:31 < gmaxwell> oh. I know whats wrong. 2^32 isn't cyclic, so none of those multipliers could actually leave the result uniform. e.g. 289^134217728 mod 2^32 = 1, 3^1073741824 mod 2^32 = 1
00:34 < sipa> you mean multiply or exponentiation?
00:43 < gmaxwell> I'm showing that the multiply by foo map for each of those produces a group of size less than 2^32-1.
00:44 < gmaxwell> which I think is a necessary condition to leave the result uniform?
00:45 < sipa> foo map?
00:45 < gmaxwell> foo being 3 or 289 above.
00:48 < sipa> hmm, i'm not convinced by that argument
00:49 < sipa> 3 mod 2^32 has a modular inverse, 2863311531
00:49 < sipa> so after multiplying by 3, i can inverse the operation by multiplying with 2863311531
00:50 < sipa> doesn't that imply that multiplication by 3 mod 2^32 is a permutation?
00:52 < sipa> it's just a permutation that undoes itself after repeating it 1073741824 times, but that doesn't mean anything
00:52 < sipa> (x ^ 1) is also a permutation; if x is uniformly distributed, (x ^ 1) is also uniformly distributed
00:53 < gmaxwell> hm. okay, thats convincing.
00:53 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
01:03 < gmaxwell> (to be clear, being a permutation isn't suffcient, cyclic rotation left by 1 bit is also a permutation, but would leave the low 6 bits highly biased)
01:05 < sipa> eh?
01:05 < gmaxwell> for a 31 bit input.
01:06 < sipa> cyclic rotation left is not a permutation mod 2^31
01:06 < sipa> multiplication with an odd number is a permutation mod every power of 2
01:08 < gmaxwell> ::nods::
01:09 < gmaxwell> I still don't know why it's failing far more often than it should.
01:09 < sipa> maybe sha256 is not as random as we thought!
01:09 < sipa> *ducks*
01:12 < sipa> gmaxwell: oh, it's looking at the up-to-6 *highest* bits of the resulting number
01:12 < sipa> it should be the lowest ones if the argument "it's a permutation mod a power of two" has to hold
01:12 < gmaxwell> it's what? damnit.
01:13 < sipa> it should not just look at the lower ones though, as that means we'd fail to detect nonuniformity there
01:14 < sipa> perhaps instead of multiplying with odd numbers we should just choose 6 random bits out of N, and look at those
01:15 < gmaxwell> it looks at all the windows 0-6) 1-7) 2-8) ... and so on. up to b-6
01:15 < sipa> yup
01:15 < sipa> i'm not convinced it's wrong
01:15 < sipa> but my argument for why it should hold is bad
01:16 < gmaxwell> well, I just tried multiplying only with 1 and it failed afer about a million trials (with 31 so the 26 shifts) which is much smaller than it should have.
01:17 < gmaxwell> sipa: If a number is uniform mode 2^n  then any window of bits inside that is uniform too.
01:20 < sipa> yup, just realized that too
01:22 < sipa> CHECK((((uint64_t)r) >> bits) == 0);
01:22 < sipa> that's undefined for bits == 32?
01:23 < sipa> oh, no, it's cast to int64 first
01:26 < gmaxwell> It fails for many different bits counts in any case, I've been testing with just 31. Even with it just set to a multiplier of 1 and b=31 only; if failed for me in about a million trials, which is far too early.
01:30 < sipa> if it also fails with lower b and multiplier, you could just test exhaustively with way more iterations and see the distribution
01:37 < sipa> oh, the iteration counts need to be higher
01:37 < sipa> they are computed to make the chance for a single (out of 64) bit pattern to not be observed go below one in a billion
01:37 < sipa> but there are 64 bit patterns
01:38 < sipa> also, doesn't account for the different multiplications
01:38 < gmaxwell> I know I said earlier it's not accounting for multiple comparisons.
01:39 < gmaxwell> But I went and redid the numbers and did, and it's still failing far more often than I expected.
01:39 < sipa> 1694 for 6, indeed
01:39 < gmaxwell> I accounted for the windows and the multipliers and got 1 in 407612 as the expected rate
01:40 < gmaxwell> of failure.
01:40 < gmaxwell> so I'm quite surprised to see it fail after a thousand or whatever.
01:41 < gmaxwell> and even with no multipliers I saw it fail after a million and after 750k
01:42 < gmaxwell> (for just running with 31)
02:13 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has joined #secp256k1
03:25 -!- nickler [~nickler@185.12.46.130] has quit [Ping timeout: 260 seconds]
03:25 -!- nickler [~nickler@185.12.46.130] has joined #secp256k1
06:32 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 260 seconds]
06:32 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
08:13 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has quit [Ping timeout: 246 seconds]
08:24 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has joined #secp256k1
09:04 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has quit [Ping timeout: 260 seconds]
09:55 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has joined #secp256k1
16:26 -!- fkhan [weechat@gateway/vpn/mullvad/x-hdxvkwzukfsqsuxc] has quit [Ping timeout: 246 seconds]
16:46 -!- fkhan [~weechat@unaffiliated/loteriety] has joined #secp256k1
17:42 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has quit [Ping timeout: 246 seconds]
17:48 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has joined #secp256k1
18:38 -!- xypher_ [~xypher@static-108-45-93-78.washdc.fios.verizon.net] has quit [Read error: Connection reset by peer]
20:52 -!- jtimon [~quassel@202.83.241.187] has joined #secp256k1
21:38 -!- jtimon [~quassel@202.83.241.187] has quit [Ping timeout: 260 seconds]
23:48 -!- jtimon [~quassel@202.83.241.187] has joined #secp256k1