mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2007-06-09, 18:01   #1
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3·73 Posts
Default New coordinate system for elliptic curves

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.
wpolly is offline   Reply With Quote
Old 2007-06-09, 18:15   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-06-10, 22:57   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3·13·197 Posts
Default

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.
Prime95 is online now   Reply With Quote
Old 2007-06-11, 14:16   #4
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

Here is another interesting paper on elliptic curves.

http://www.ams.org/bull/2007-44-03/S...53-6/home.html
Zeta-Flux is offline   Reply With Quote
Old 2007-07-18, 00:12   #5
tanjalange
 

7×487 Posts
Default New version of paper available

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.

Quote:
Originally Posted by wpolly View Post
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.
  Reply With Quote
Old 2007-07-18, 13:18   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by tanjalange View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Testing Mersenne Primes with Elliptic Curves a nicol Math 3 2017-11-15 20:23
Elliptic curve arithmetic burrobert GMP-ECM 6 2012-11-08 13:05
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
Elliptic Curve Arithmetic Raman Math 8 2009-04-13 19:20
Elliptic curves in NFS otkachalka Factoring 5 2005-11-20 12:22

All times are UTC. The time now is 16:36.


Fri Dec 3 16:36:57 UTC 2021 up 133 days, 11:05, 2 users, load averages: 0.93, 1.05, 1.07

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.