[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

Ron Garret ron at flownet.com
Thu Nov 3 14:07:42 PDT 2016


[cc’ing the list at Andrew’s suggestion]

Thanks!  That is exactly the kind of explanation I was looking for.  (Thanks also to Robert Ransom who also responded off-list.)

On Nov 3, 2016, at 1:54 PM, Andrew Egbert <backuntri at gmail.com> wrote:

> Ah- must have unsubscribed or something (feel free to post this to the list). I can try to explain intuitively whats happening, and why the degree of the polynomial decreases. 
> Imagine you have a curve of some sort in 2-dimensions, this will be an equation with x, y (two variables). Now imagine you look at the curve in three dimensions.
> If it really is still a one-dimensional object, it will need to have 3 variables (otherwise it will be a surface if ‘z’ is not specified).  
> 
> Resolving singularities of curves is often (not always) a similar process. Imagine you have a curve with a ‘cusp’ which is sort of like a sharp ‘singular’ point.
> (You can google image search plane curve cusp to get an idea)
> Now imagine that instead of a sharp point, you are actually looking at a place where the curve is going ‘downwards’ in a third dimension (so in fact it is a smooth curve).
> This is sort of what’s happening. 
> Best, 
> Andrew
> 
>> On Nov 3, 2016, at 1:48 PM, Ron Garret <ron at flownet.com> wrote:
>> 
>> Not sure what “bad response” you’re referring to here because this is the only message I’ve received from you.  I took a look at page 1, and I do understand the change of variables that transforms curve25519 into Ed25519 and vice-versa.  It’s the more general case that I don’t yet fully understand.
>> 
>> I have a working theory though: because the transformation involves a change of variables, the letters X and Y have completely different semantics in the Edwards formula than in the other forms.
>> 
>> On Nov 3, 2016, at 1:36 PM, Andrew Egbert <backuntri at gmail.com> wrote:
>> 
>>> Sorry that was a bad response, since I missed the last sentence of your post- I’ve written out the transformation on page 1 of my thesis here: https://divisibility.files.wordpress.com/2016/02/thesismarch18.pdf (also available at my github)
>>>> On Nov 3, 2016, at 12:30 PM, Ron Garret <ron at flownet.com> wrote:
>>>> 
>>>> 
>>>> On Nov 1, 2016, at 2:40 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>>> 
>>>>> It would be be great if there were better surveys on modern ECC and
>>>>> engineering issues.  If someone wanted to suggest a reading list /
>>>>> bibliography that would be a nice contribution (but also a bunch of
>>>>> work).
>>>> 
>>>> I decided it would be a useful exercise for me to undertake to write such a survey (even if I couldn’t actually finish it), and right away I ran into a snag.  I was trying to reconcile all the different forms of elliptic curve formulas commonly found in the literature, and found the following promising-looking lead on mathworld:
>>>> 
>>>> http://mathworld.wolfram.com/EllipticCurve.html
>>>> 
>>>> Ax^3 + Bx^2y + Cxy^2 + Dy^3 + Ex^2 + Fxy + Gy^2 + hHx + Iy + J = 0
>>>> 
>>>> This is consistent (AFAICT) with the definition given in section 4.4.2.a of Cohen and Frey.  But then there are Edwards curves, which have a x^2y^2 term in them.  How do those fit in?
>>>> 
>>>> In fact, as I started thinking about this I realized that Edwards curves are really weird because they’re quartic and not cubic (aren’t they?) and all elliptic curves are supposed to be cubic (aren’t they?)  How can a fourth-order polynomial be birationally equivalent to a third-order polynomial?
>>>> 
>>>> I tried taking a look at some of the proofs that Edwards curves are birationally equivalent to Montgomery curves but they went way over my head.  Is there a more elementary way of understanding this?
>>>> 
>>>> Thanks,
>>>> rg
>>>> 
>>>> _______________________________________________
>>>> Curves mailing list
>>>> Curves at moderncrypto.org
>>>> https://moderncrypto.org/mailman/listinfo/curves
>>> 
>> 
> 



More information about the Curves mailing list