--- Log opened Fri May 10 00:00:11 2019 03:10 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection] 03:10 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1 03:50 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 252 seconds] 03:53 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1 13:49 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-qjwzupuoswkmglui] has joined #secp256k1 13:58 < elichai2> sipa: If I may disturb you again, why in signing you use the jacobi symbol? is there a logic on when you use QR,Jacobi,Lower etc.? (if you wrote a paper explaning your decisions in BIP schnorr I would love to read it) 13:58 < sipa> elichai2: i think the justifications are in the bip? 14:00 < sipa> 3. Implicitly choosing the Y coordinate that is a quadratic residue (has a square root modulo the field size)[4]. 14:00 < sipa> The third option is slower at signing time but a bit faster to verify, as the quadratic residue of the Y coordinate can be computed directly for points represented in Jacobian coordinates (a common optimization to avoid modular inverses for elliptic curve operations). The two other options require a possibly expensive conversion to affine coordinates first. 14:01 < elichai2> but if i understand correctly jacobi symbol isn't a way to check for quadratic residue 14:02 < sipa> yes it is\ 14:03 < sipa> the jacobi symbol is 1 for quadratic residues, 0 for 0, and -1 for quadratic nonresidues 14:03 < sipa> if that isn't clear perhaps we should update the bi[ 14:04 < elichai2> yeah I searched `jacobi` in the bip and couldn't find it in relation to the quadratic residue 14:05 < sipa> ah sorry, it's the same 14:05 < sipa> at least when the modulus is prime 14:05 < elichai2> I'm trying to learn all this math without a math degree so edge things like jacobi symbol are new to me andi'm learning along the way by trying to implement it all (non production of course) 14:10 < elichai2> sipa: hmm 9 mod 13 has Jacobi Symbol of 1, but also (13-9) mod 13 which is 4 has Jacobi 1 (which is the n-k) 14:10 < sipa> -1 is a quadratic residue mod 13, so negating a number does not change its jacobi symbol mod 13 14:11 < sipa> -1 is not a quadratic residue mod (secp256k1's field size) 14:11 < sipa> jacobi(a*b mod m) = jacobi(a mod m)*jacobi(b mod m) 14:15 < elichai2> ohhh in secp256k1 one of the Y's *must* be a QR because the equation is squared. right? 14:15 < sipa> yes, but only becuase -1 is not a QR mod secp256k1's field size 14:15 < sipa> this is not generally true for all curves 14:17 < elichai2> I think I understand now, thanks for your time :) (If you have a source/book suggestion to learn all these little details would love to get, learning the general EC math is easy but I can't know about things like QR and Jacobi without encountering them somewhere) 14:17 < elichai2> sipa: nor for all fields 14:20 < sipa> right 14:21 < sipa> elichai2: in fact, -1 is a quadratic residue mod p if and only if (p mod 4 = 1) 14:24 < elichai2> hmm, ok 17:52 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-qjwzupuoswkmglui] has quit [Quit: Connection closed for inactivity] 18:21 < gmaxwell> Hm. Anyone have any citations for the user of overcomplete representations for field elements for carry reduction? 18:21 < gmaxwell> https://github.com/bitcoin-core/secp256k1/issues/615 18:28 < sipa> i think i originally learned about that technique from an ed25519 paper 18:35 < gmaxwell> I wrote a bit of an answer 18:51 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection] 18:52 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1 22:17 -!- cornfeedhobo [~cornfeedh@unaffiliated/cornfeed] has quit [Read error: Connection reset by peer] 22:30 -!- cornfeedhobo [~cornfeedh@unaffiliated/cornfeed] has joined #secp256k1 22:50 -!- BlueMatt_ [~BlueMatt@ircb.bluematt.me] has joined #secp256k1 22:51 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has quit [Ping timeout: 258 seconds] --- Log closed Sat May 11 00:00:09 2019