--- Day changed Tue Dec 29 2015
03:40 < gmaxwell> https://gist.github.com/bishboria/8326b17bbd652f34566a
03:40 < gmaxwell> "Springer have made a bunch of books available for free"  some of these are relevant to our interests.
04:07 < gmaxwell> There are many more than are listed at that page... every springer textbook >10 years old.
04:19 -!- maaku [~quassel@botbot.xen.prgmr.com] has quit [Remote host closed the connection]
05:27 -!- GAit [~GAit@2.230.161.158] has joined #secp256k1
05:32 -!- maaku [~quassel@botbot.xen.prgmr.com] has joined #secp256k1
05:32 -!- maaku is now known as Guest87480
05:33 -!- Guest87480 is now known as maaku
05:48 -!- GAit [~GAit@2.230.161.158] has quit [Quit: Leaving.]
05:49 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
06:42 < midnightmagic> I can download fulltext of many of those books by the way; I would be happy to see what I can grab if people have specific chapters, or books.
06:42 < midnightmagic> ..  in mind.
07:35 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
07:35 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
08:47 < andytoshi> downloading everything from that page .. will ask at ##hplusroadmap about finding more
08:47 < andytoshi> i've got lots of space but little bandwidth unfortunately
08:52 < gmaxwell> that page doesn't list but a fraction of whats available. I wouldn't bother downloading anything on that page that you don't immediately want-- lots of people have all thats there.
09:31 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
09:52 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
10:09 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
10:09 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
10:36 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Read error: Connection reset by peer]
10:37 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
10:37 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Client Quit]
13:12 -!- fkhan_ [~weechat@unaffiliated/loteriety] has quit [Ping timeout: 272 seconds]
13:23 -!- fkhan_ [weechat@gateway/vpn/mullvad/x-fgvzvpcisbnqjtpl] has joined #secp256k1
17:40 < andytoshi> am i remembering the effective affine trick correctly: the map (x, y, z) → (x, y, Kz) is an isomorphism onto the curve y^2 = x^3 + 7(Kz)^6 for any K in our field
17:40 < andytoshi> (everything in jacobi coordinates, so our original curve eqn is y^2 = x^3 + 7z^6)
17:40 < sipa> i believe so
17:40 < andytoshi> hmm
17:41 < sipa> for any non-zero K :)
17:41 < andytoshi> yes :)
17:41 < andytoshi> so, beta (= 1^{1/3} in the field) has a square root (which is beta+1 lol, tho i don't think this matters)
17:41 < andytoshi> so using K = beta+1, it seems like we get an endomorphism of order 6
17:41 < andytoshi> which is given by (x,y,z) -> (x,y,(beta + 1)z)
17:42 < andytoshi> and the square of this endomorphism is the (inverse of the) classic x → beta*x endomorphism
17:46 < andytoshi> im fairly sure i'm correct, and this endomorphism corresponds to multiplication by sqrt(lambda) in the group (and such a sqrt does exist according to sage ... as it should, i'd be very confused otherwise)
17:48 < andytoshi> so i have a bunch of questions: (a) does having two endomorphisms give us twice the optimization? i guess no since these aren't actually independent endomorphisms, one is the square of the other. (b) does having an endomorphism of order 6 help us? like could we split scalars as x = x1 + x2*sqrt(lambda) + x3*lambda + ... + x5*sqrt(lambda)^5. (c) independently of all that can we evade patent concerns by
17:48 < andytoshi> using sqrt(lambda) since this is technically a different endomorphism
17:48 < gmaxwell> andytoshi: it depends on what the lattice looks like that you can construct with it.
17:49 < gmaxwell> using p, lambda, lambda^2 didn't result in a useful latice; for example.
17:49 < andytoshi> can you say why not?
17:49 < andytoshi> i don't have a good understanding of that
17:49 < sipa> my intuition is that lambda^2 is not sufficiently independent from lambda to be useful
17:49 < gmaxwell> I'm not sure how you'd say it in number theory; but it's because it doesn't result in a orthorgonal basis.
17:50 < andytoshi> well we have a 1-dimensional space, nothing is gonna be orthogonal. but we get "computational orthogonality" because DL is hard (or rather, because x -> xG "looks random")
17:50 < andytoshi> was my intuition
17:50 < andytoshi> am i way off-base there?
17:51 < andytoshi> oh, i get it, 1 + beta + beta^2 = 0
17:51 < andytoshi> hmmm. so i think there is no such relation between 1, beta, beta^{3/2}
17:52 < andytoshi> for those following at home: (1 + beta + beta^2) = (1 - beta^3) / (1 - beta) = 0 / (1 - beta) = 0
17:53 < andytoshi> if im right we can get a 3d lattice here and get some extra optimization, assuming the scalar split can be similarly efficiently computed (this is still black magic to me)
17:54 < sipa> i was able to re-do the work that Hal did to find the constants for secp256k1 in any case
17:54 < sipa> and gmaxwell as well, i guess
17:54 < andytoshi> but there will be constants?
17:57 < gmaxwell> andytoshi: nah, you can't.  alas.  The endomorphism is order 3.  1 == lambda^3, lambda, lambda^2  .. sqrt(lambda) == lambda^2
17:58 < andytoshi> hah derp
17:58 < sipa> so 1, beta, beta^{3/2} is really just 1, beta, 1?
17:58 < andytoshi> yeah, or 1,beta,-1
17:58 < andytoshi> i should've seen that :)
17:58 < andytoshi> my head is a bit fuzzy now (been reading textbooks all day :)) but i have an idea we sholud be only able to get a phi(6) = 2-dimensional lattice, even from a order-6 endomorphism ... so i would've been SOL anyway
17:59 < gmaxwell> Though yes, if we were able to get two distinct endomorphisms we could get more speedup. This is the motivation between GLV/GLS curves that have two.
18:01 < gmaxwell> E.g. http://eprint.iacr.org/2008/194
18:04 < andytoshi> ok. and i have a pretty clear idea intuition that our curve only has endomorphisms of order 2 and 3. (the order 2 one is P → -P). composing them will get you order-6, but this won't give you more than a 2D lattice (abstractly cuz i think an order-N endomorphism will get you a phi(N)-dimensional lattice over Z, concretely cuz you go from (x, y) -> (x, -y) by multiplying by -1, which obviously is generated
18:04 < andytoshi> by 1)
18:04 < andytoshi> alaso
18:04 < andytoshi> alas
18:05 < gmaxwell> yea, we already make use of the fact that -1 is cheap in any case... thats the motivation for signed digit representations.
18:05 < andytoshi> the "only order 2 and 3" comes from the fact that y^2 = x^3 + 6Kz^6 is isomorphic to our curve iff K is a sixth power, which comes from one of the effective-affine papers
18:05 < andytoshi> damn :/
18:07 < gmaxwell> what if K is rational? does the extension provide more possibilities?
18:14 < andytoshi> i think no. i'm having trouble coming up with a clear reason why tho
18:14 < andytoshi> in fact i think even adjoining weird roots to our field will be insufficient
18:15 < andytoshi> by "K rational" you mean like it's a fraction? given that we're working over a finite field i don't think that adds anything
18:16 < gmaxwell> yea, I was about to say that myself. "duh, the size of the rationals isn't any larger"
18:18 < andytoshi> so a weird fact is that our field already has a nontrivial 7th root of 1. i'm musing on why i can't multiply z by that to get a order-7 endomorphism
18:18 < andytoshi> (our group order does not admit a 7th root, so such an endomorphism clearly does not exist ... but how?)
18:18 < gmaxwell> because of the ^3 in the curve equation.
18:19 < andytoshi> oh, i see
18:19 < andytoshi> ok, but by the effective-affine trick this does take us to an isomorphic curve
18:19 < andytoshi> so we have these 7 curves we can cycle through
18:20 < andytoshi> oh, but we've talked about this. using different curves means that scalar-splitting makes no sense (or at least, we could make no sense of it)
18:21 < gmaxwell> well I think we talked about it for EA in general.
18:23 < andytoshi> yeah. but the reasoning was the same .. if we use an isomorphism rather than endomorphism we have to "come back" in the end so we can't do meaningfully different computations on the other curve