--- 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