--- Day changed Fri Oct 23 2015
02:20 -!- maaku [~quassel@botbot.xen.prgmr.com] has quit [Read error: Connection reset by peer]
02:21 -!- maaku__ [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has quit [Ping timeout: 265 seconds]
02:21 -!- maaku [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has joined #secp256k1
02:22 -!- maaku is now known as Guest6474
02:22 -!- maaku__ [~quassel@botbot.xen.prgmr.com] has joined #secp256k1
03:01 -!- GAit_Alt [~GAit@2-228-102-100.ip191.fastwebnet.it] has joined #secp256k1
03:03 -!- gmaxwell_ [greg@mf4-xiph.osuosl.org] has joined #secp256k1
03:03 -!- gmaxwell_ is now known as Guest25067
03:04 -!- wump [~quassel@pdpc/supporter/professional/wumpus] has joined #secp256k1
03:07 -!- Netsplit *.net <-> *.split quits: wumpus, GAit, midnightmagic, gmaxwell
03:07 -!- GAit_Alt is now known as GAit
03:08 -!- Netsplit over, joins: midnightmagic
03:23 -!- GAit [~GAit@2-228-102-100.ip191.fastwebnet.it] has quit [Ping timeout: 260 seconds]
03:28 -!- GAit [~GAit@2-228-102-100.ip191.fastwebnet.it] has joined #secp256k1
04:03 -!- wump is now known as wumpus
07:35 <@andytoshi> sipa: gmp can do a legendre symbol check *way* faster than inversion (something like 10-20% of the time IIRC), but i understand how only on a pretty high level
07:35 <@andytoshi> sipa: my current code does modular inversion and legendre at the same speed
07:36 < sipa> andytoshi: and what is that speed? :)
07:37 <@andytoshi> sipa: one sec :)
07:39 < sipa> so my reasoning is that if instead of "R.y is implicitly even", we use "R.y impkicitly has legendre symbol 1"
07:39 <@andytoshi> sipa: with GMP field inversion takes 2.97us, legendre 0.140
07:40 < sipa> for recovery this does not change much, as you can always instead of a square root compute a quartic root  and square it... this always results in the square root which itself has a square root
07:41 < sipa> but for normal verification, you can skip the inversion
07:41 <@andytoshi> with my code, field inversion is 4.94us, legendre is 7.8 :P
07:42 < sipa> if y = Y/Z^3, then legendre(y) = legendre(Y*Z)
07:43 <@andytoshi> field multiply is 0.0284us for reference
07:44 < sipa> gah, so we really need fast legendre :)
07:44 < sipa> but do you agree with my reasoning?
07:45 <@andytoshi> yeah, sorry :). i have been really taken up with other projects lately. fast legendre will require a fair bit of studying (well, a week or two. not months or years :))
07:45 <@andytoshi> yes
07:45 < sipa> that computing the square root which also has a square root is cheap
07:45 < sipa> and that legendre of y can be conputed without inversion
07:46 <@andytoshi> the fourth root costs the same as current const-time sqrt?
07:46 <@andytoshi> i agree that legendre(y) requires no inversion yeah
07:47 < sipa> the fourth root is just computing a^((p+1)/8)
07:47 <@andytoshi> right
07:47 < sipa> instead of a^((p+1)/4)
07:47 <@andytoshi> understood
07:48 < sipa> i don't quite understand how computing that, and squaring it, gives a different result from a^((p+1)/4)
07:49 <@andytoshi> yeah, i read that in the scrollback. i'm a bit confused also
07:54 < sipa> ha
07:54 < sipa> i get it
07:55 < sipa> a^((p+1)/4) already always gives a result with legendre symbol 1
07:55 <@andytoshi> ah, i thought as much
07:55 <@andytoshi> then i thought "but if it gives the square root, and every number can be a square root, doesn't this imply all numbers have legendre symbol 1?"
07:56 < sipa> so yes, that is cheap :p
07:56 <@andytoshi> and now i'm reading "why the (p-1)/4 thing works without any high algebra" post at https://bitcointalk.org/index.php?topic=1133575.msg11971722#msg11971722 and thinking about that..
07:56 < sipa> it gives a square root, but every number that has a root has two
07:56 <@andytoshi> ah!
07:57 < sipa> so it gives precisely the one  of those two with legendre symbol 1
07:57 <@andytoshi> getcha, i'm happy now
07:57 < sipa> awesome
08:02 < sipa> i guess you can speed up legendre computation by having a table of (a/n) for various low values of a and n
08:02 <@andytoshi> i'm unsure, i haven't tried it. i think not because my code recognizes when the numbers are small enough to fit in one word and switches to primitive int math
08:03 <@andytoshi> so it'd save log(an) loop iterations on uint64_ts
08:03 <@andytoshi> or something like that
08:13 < sipa> so!
08:14 < sipa> a^((p+1)/2) is either equal to a or to -a, and alwayys has legendre symbol 1
08:18 <@andytoshi> yeah. very cool
08:19 <@andytoshi> it's like how sqrt(x^2) acts as an absolute value operator on the reals
08:19 < sipa> exactly
08:20 < sipa> makes sense, as the legendre symbol is actually defined as a^((p-1)/2)
08:20 < sipa> so multiplying that with a gives a^((p+1)/2)
08:28 <@andytoshi> yup. the analogy with sign is actually really strong, i think i'm gonna start thinking of the legendre symbol as being a sign
08:28 <@andytoshi> at least for this field
08:29 < sipa> indeed
08:49 -!- maaku__ is now known as maaku
09:40 < Guest25067> Fortunately secp256k1's field is also congruent to 7 mod 8.
09:40 < Guest25067> oh darn
09:40 -!- Guest25067 [greg@mf4-xiph.osuosl.org] has quit [Changing host]
09:40 -!- Guest25067 [greg@wikimedia/KatWalsh/x-0001] has joined #secp256k1
09:40 -!- Guest25067 is now known as gmaxwell
10:07 < sipa> indeed
11:07 -!- fkhan [weechat@gateway/vpn/mullvad/x-skroeccqmaqfpcro] has quit [Ping timeout: 260 seconds]
11:21 -!- fkhan [weechat@gateway/vpn/mullvad/x-wbcbtnufevfsefeb] has joined #secp256k1
12:09 -!- fkhan [weechat@gateway/vpn/mullvad/x-wbcbtnufevfsefeb] has quit [Ping timeout: 252 seconds]
12:26 -!- fkhan [weechat@gateway/vpn/mullvad/x-pafengwxecqdlpgq] has joined #secp256k1
13:37 < gmaxwell> sipa: Your comment that there is no point with x=1 is incorrect, https://bitcoin.stackexchange.com/questions/38513/the-shortest-ecdsa-signature/38521
13:39 < gmaxwell> (there is no point with x=0, which is probably what you were thinking, but there could still be an r=zero (due to the modular reduction) except for that being prohibited by a seperate test)
13:42 < sipa> feel free to comment there :)
13:43 < sipa> i actually thought that there was no x=1 on the curve
13:43 < sipa> though maybe there is a x+order on the curve
13:45 < gmaxwell> sage: C.lift_x(1)
13:45 < gmaxwell> (1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534 : 1)
13:46 < gmaxwell> (we also have tests for both pubkey loading with x=1 and for the smallest signature value possible)
13:46 < sipa> stand corrected, i do
16:52 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Read error: Connection reset by peer]
16:58 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
20:30 -!- Guest6474 [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has quit [Ping timeout: 265 seconds]
20:30 -!- maaku__ [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has joined #secp256k1
21:19 -!- maaku [~quassel@botbot.xen.prgmr.com] has quit [Read error: Connection reset by peer]
21:27 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Remote host closed the connection]
21:31 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1