--- Log opened Tue Jun 22 00:00:45 2021
00:35 -!- belcher_ is now known as belcher
09:52 < roconnor> Is there a general relationship between/for finding isomorphic curves on the Fp plane?
10:00 < sipa> if they're cyclic and their order is the same, they are isomorphic ;)
10:01 < roconnor> There are comments like this:
10:01 < roconnor>     /*
10:01 < roconnor>      * Perform the additions on an isomorphism where 'd' is affine: drop the z coordinate
10:01 < roconnor>      * of 'd', and scale the 1P starting value's x/y coordinates without changing its z.
10:01 < roconnor>      */
10:02 < roconnor> Which suggests that if you take a point (x,y) and transform it into (x*z^2, y*z^3) for some non zero z value, you will get another point on an isomorphic curve.
10:02 < roconnor> I mean, maybe... I'm not sure.
10:03 < sipa> Ah, that's correct, but only on y^2=x^3+b curves
10:04 < roconnor> Is there a simple argument to why this works?
10:04 < sipa> Let's see.
10:04 < sipa> (x,y) is on the curve y^2 = x^3 + b
10:06 < sipa> no, let's start with (x,y,z) is a point on the Jacobian variant of our curve, so (y/z^3)^2 = (x/z^2)^3 + b, or (ignoring infinity), y^2 = x^3 + b*z^6
10:06 < sipa> in other words, (x,y) is on the curve y^2 = x^3 + (b*z^6) ?
10:07 < sipa> i guess you'd need to show that point addition/doubling is also transformed the same way
10:08 < sipa> which is easy for addition, because b does not appear in the point addition formula
10:09 < sipa> or in the doubling formula
10:11 < sipa> that's sufficient, i think?
10:12 < roconnor> I mean, adding and doubling doesn't preserve the z coordinate, so I guess I don't really follow your argument.
10:15 < sipa> i try again
10:23 < sipa> let's say E_t is the affine curve of points (x,y) for which y^2 = x^3 + b*t^6, with addition formula (x1,y1) + (x2,y2) = (x3,y3) where x3 = l^2 - (x1+x2), y3 = l*(x1-x3)-y1, l=(y2-y1)/(x2-x1) and doubling formula the same but l=3*x1^2/(2*y1)
10:24 < sipa> note that t does not occur in either formula
10:33 < sipa> Now i claim that there is an isomorphism from E_t1 to E_t2, namely f((x,y)) = (x*(t2/t1)^2, y*(t2/t1)^3)
10:35 < roconnor> I see, it is a linear transformation, so it maps lines to lines, and lines are what define point addition.
10:36 < sipa> i hadn't thought about it that way, but indeed!
10:36 < roconnor> so any linear transformation that takes points on one curve all on one b1 values to points that all are on another b2 value will work.
10:38 < roconnor> I guess we want an injective linear transformation if we want an isormorphism, so it ought to be non-sigular linear transfromatoin.
10:39 < sipa> so in the addition formula, l will map to l*t2/t1, and thus x3 will map to x3*(t2/t1)^2
10:40 < sipa> and y3 to y3*(t2/t1)^3
10:43 < sipa> put otherwise, if C_b is the curve (x,y) : y^2 = x^3 + b, then there is an isomorphism from C_b1 to C_b2 if (b2/b1) has both a cube and a square root, with mapping f((x,y)) = (x*cbrt(b2/b1),y*sqrt(b2/b1))
10:51 < roconnor> I guess about 1/6 of the values in F_p are of the form z^6.
10:51 < sipa> i think exactly 1/6, actually
10:52 < roconnor> F_p isn't a multiple of 6.
10:52 < roconnor> I mean p isn't a multiple of 6.
10:52 < sipa> excluding 0
10:52 < roconnor> I guess it also isn't a coincidence that there are 6 classes of elliptic curves.
10:53 < roconnor> Now I see why there are so few classes.
10:53 < sipa> indeed
10:53 < sipa> of form y^2 = x^3 + b, you mean?
10:53 < roconnor> yes I was about to add that.
11:01 < sipa> so the remarkable thing is that this works without change in the formulas, so all the existing affine point addition/doubling code can be used with (x,y) for which (x,y,z) is a point on the jacobian secp curve, and it computes the correct results on said isomorphic curve
11:02 < sipa> all you need is get all your input points on the same z "denominator", drop the Z, use affine formulas for all arithmetic, and finally multiply the dropped z back in
11:02 < sipa> that's the "effective affine" optimization peter dettman came up with
11:15 -!- belcher [~belcher@user/belcher] has quit [Quit: Leaving]
13:19 -!- belcher [~belcher@user/belcher] has joined #secp256k1
17:07 -!- belcher_ [~belcher@user/belcher] has joined #secp256k1
17:11 -!- belcher [~belcher@user/belcher] has quit [Ping timeout: 252 seconds]
18:20 -!- jesseposner [~jesse@2601:647:0:89:6de9:9aa6:8bb7:1691] has quit [Ping timeout: 250 seconds]
18:21 -!- jesseposner [~jesse@2601:647:0:89:dcb5:c682:ac61:4798] has joined #secp256k1
--- Log closed Wed Jun 23 00:00:46 2021