New coordinate system for elliptic curves

[wpolly]

In http://cr.yp.to/newelliptic/newelliptic-20070522.pdf
Bernstein and Lange described a new elliptic curve coordinte system which costs 3M+4S per doubling and 11M+1S per multiplication.

I wonder if this could be faster than Montgomery coordinate and addition-subtraction chains that is currently used in GMP-ECM.

[akruppa]

Thanks for this link. We've been toying with the idea of using a sliding window multiplication with Weierstraß coordinates before. These new parameters seem like they could help speed that up, specifically they need no inversions which means we could do one curve at a time and choose a larger window size with a given amount of memory. I can't say anything about whether that will actually be faster than Montgomery's curves with PRAC, but it sounds very worthwhile to look into.

Alex

[Prime95]

On another note, have there been any improvements to PRAC in the last decade?

I doubt it, but I'll ask: Have there have been any improvements to ell_dbl and ell_add which are 10 and 12 transforms in prime95.

[Zeta-Flux]

Here is another interesting paper on elliptic curves.

http://www.ams.org/bull/2007-44-03/S...53-6/home.html

Dan and I just posted an updated version at
http://www.hyperelliptic.org/tanja/newelliptic/
and
http://cr.yp.to/newelliptic/

We discuss single and multi-scalar multiplication and show that for window widths >= 4 and general basepoint Edwards curves are faster than Montgomery curves with general basepoint.

We're now looking into applications outside ECC including ECM and ECPP.

Originally Posted by wpolly

In http://cr.yp.to/newelliptic/newelliptic-20070522.pdf
Bernstein and Lange described a new elliptic curve coordinte system which costs 3M+4S per doubling and 11M+1S per multiplication.

I wonder if this could be faster than Montgomery coordinate and addition-subtraction chains that is currently used in GMP-ECM.

[R.D. Silverman]

Originally Posted by tanjalange

Dan and I just posted an updated version at
http://www.hyperelliptic.org/tanja/newelliptic/
and
http://cr.yp.to/newelliptic/

We discuss single and multi-scalar multiplication and show that for window widths >= 4 and general basepoint Edwards curves are faster than Montgomery curves with general basepoint.

We're now looking into applications outside ECC including ECM and ECPP.

This is really nice. Kudos.

Is anything known about pre-selecting the Edwards curve parameters so that
the Torsion subgroup has a specified order? The Montgomery parameterization allows us (as you know) to find curves whose order is divisible by 12 (or 16 half the time and 8 half the time). This gives an
extra digit "for free" in the factor being sought.

If Edwards curves can not be thusly parameterized, it may negate their
advantage of fewer multiplications.