--- Log opened Sat Jun 15 00:00:47 2019
00:20 -!- midnightmagic [~midnightm@unaffiliated/midnightmagic] has quit [Ping timeout: 252 seconds]
00:26 -!- midnightmagic [~midnightm@unaffiliated/midnightmagic] has joined #secp256k1
08:28 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-fpqipyabnikfnatg] has joined #secp256k1
10:35 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-fpqipyabnikfnatg] has quit [Quit: Connection closed for inactivity]
11:05 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-awfcdxfnhqfaojku] has joined #secp256k1
13:25 < elichai2> in schnorr secp256k1 Jacobi==Legendre right? (because the p is an odd prime)
13:28 < sipa> yup
13:35 < elichai2> hmm so I guess that in reality `secp256k1_num_jacobi` is a bit too generic
13:36 < sipa> why?
13:37 < sipa> it computes the jacobi symbol for any number, not just odd primes
13:38 < elichai2> because it's generalized to the Jacobi symbol. which is "harder" to compute (but I guess the difference is negligible)
13:38 < sipa> actually, no
13:39 < sipa> computing the legendre symbol is usually done using a jacobi algorithm
13:40 < elichai2> really? I guess I looked until now only on naive implementations which in them you can remove the whole `a==0` / `n==1` option
13:40 < elichai2> (being a/n)
14:01 < sipa> how so?
14:02 < sipa> https://github.com/bitcoin/bitcoin/blob/master/test/functional/test_framework/key.py#L28L47
14:03 < sipa> note that during the execution, both k and n are modified the whole time
14:03 < sipa> so you know that the initial value for k is prime, but this doesn't remain true during the rest of the execution
14:12 < elichai2> I was actually looking at this implementation https://cryptocode.wordpress.com/2008/08/16/jacobi-symbol/
14:12 < sipa> same
14:12 < sipa> it has recursive calls to itself
14:12 < sipa> with different arguments
14:13 < elichai2> ohh you're right. so one of the recursive calls will not be odd prime
14:14 < sipa> most won't
14:17 < elichai2> is there any big advantage for this over restricting to be lower than half of the group order? or is that somehow totally different?
14:34 -!- roconnor [~roconnor@host-192.252-160-240.dyn.295.ca] has quit [Quit: Konversation terminated!]
14:45 < sipa> how'd that help?
15:16 < elichai2> sipa: couldn't you replace `Let k = k' if jacobi(y(R)) = 1, otherwise let k = n - k' .` with `Let k = k' if y(R)<(order/2), otherwise let k = n - k' .`. I understood that the motivation of this was to prevent malleability, so shouldn't that also do the trick?
15:16 < sipa> elichai2: that's explained in bip-schnorr
15:20 < sipa> in particular the 3 possible choices for the implicit Y coordinate in the design section
15:27 < elichai2> oh. even though I read the BIP multiple times already I somehow missed that. so you're saying that when a point is represented in Jacobian coordinates(which they already are in secp) it's faster to check the jacobi symbol instead of just checking if it's odd?
15:29 < elichai2> even thought in nickler code in the end the verification still calls `secp256k1_fe_is_quad_var`?
15:29 < elichai2> Now I really don't get it lol
15:49 < sipa> ha, maybe nickler's code doesn't implement that
15:50 < sipa> actually, it would still use fe_is_quad_var
15:50 < sipa> jacobi(y/z^3) = jacobi(y*z)
15:51 < sipa> so you don't need to compute 1/z
16:03 < elichai2> My intuition still tells me that checking for oddness is easier (just checking the last bit)
16:06 < sipa> yes, but you need to compute the oddness of y/z^3
16:06 < sipa> while the jacobi symbol of y/z^3 you can compute without any inverse
16:09 < sipa> so you're comparing (a) cubing, dividing, checking bit vs (b) multiplying, jacobi symbol
16:11 < sipa> inverting is more expensive than jacobi symbol already
16:16 < elichai2> oohhhhh right. because while verifying you don't have Ry on hand.  thanks
19:54 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 246 seconds]
19:59 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
20:15 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-awfcdxfnhqfaojku] has quit [Quit: Connection closed for inactivity]
--- Log closed Sun Jun 16 00:00:45 2019