448,959 Members | 1,196 Online
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,959 IT Pros & Developers. It's quick & easy.

# Elliptic Code

 P: n/a Hi Does anyone have/know of a python implementation of the elliptic curve factoring algorithm (lenstra) which is both: simply and cleanly coded functional I'm aware of William Stein's code (from elementary number theory book) but I don't understand his coding style and the algorithm doesn't seem to work efficiently. For that matter has anyone come across any useable math/number theory packages apart from nzmath or aladim? Thanks Phil Jul 18 '05 #1
5 Replies

 P: n/a "Philip Smith" writes: Does anyone have/know of a python implementation of the elliptic curve factoring algorithm (lenstra) which is both: simply and cleanly coded functional It's not in Python but take a look at Mike Scott's C++ implementation in MIRACL, http://indigo.ie/~mscott/ It's the simplest and most direct implementation I know of, just the bare essentials. It could probably be translated into Python pretty straightforwardly. I'm aware of William Stein's code (from elementary number theory book) but I don't understand his coding style and the algorithm doesn't seem to work efficiently. A high performance implementation means complicated code, e.g. Peter Montgomery has done a few of those. If it's for instructional purposes I think the MIRACL version is far more understandable even if it's slower. If you mean you don't understand the algorithm, try Neal Koblitz's book "A Course in Number Theory and Cryptography". It has no code but it explains the algorithm in a pretty accessible way. Jul 18 '05 #2

 P: n/a thanks for the suggestion I understand the algorithm quite well but how to code the multiplication stage most efficiently in python eludes me. William Stein's code is obviously not high performance because in the region where ecm should do well (30-40 dec digits) my python implementation of the rho algorithm blows it away. In terms of factoring implementations generally (in python) I think nzmath's mpqs is brilliant - and it has such a small footprint I can run it in 10 threads at once. anyway - I'll have a look at MIRACL (I have the library but have never used it yet. Phil wrote in message news:m3************@localhost.localdomain... "Philip Smith" writes: Does anyone have/know of a python implementation of the elliptic curve factoring algorithm (lenstra) which is both: simply and cleanly coded functional It's not in Python but take a look at Mike Scott's C++ implementation in MIRACL, http://indigo.ie/~mscott/ It's the simplest and most direct implementation I know of, just the bare essentials. It could probably be translated into Python pretty straightforwardly. I'm aware of William Stein's code (from elementary number theory book) but I don't understand his coding style and the algorithm doesn't seem to work efficiently. A high performance implementation means complicated code, e.g. Peter Montgomery has done a few of those. If it's for instructional purposes I think the MIRACL version is far more understandable even if it's slower. If you mean you don't understand the algorithm, try Neal Koblitz's book "A Course in Number Theory and Cryptography". It has no code but it explains the algorithm in a pretty accessible way. Jul 18 '05 #3

 P: n/a Philip Smith wrote: I understand the algorithm quite well but how to code the multiplication stage most efficiently in python eludes me. You might want to look at http://gmpy.sourceforge.net/ It has very fast multiplication up to any size you like! -- Nick Craig-Wood -- http://www.craig-wood.com/nick Jul 18 '05 #4

 P: n/a Nick Craig-Wood writes: I understand the algorithm quite well but how to code the multiplication stage most efficiently in python eludes me. You might want to look at http://gmpy.sourceforge.net/ It has very fast multiplication up to any size you like! I think he's talking about point multiplication on the elliptic curve group, not integer multiplication. Jul 18 '05 #5

 P: n/a Quite so - but thanks for your help in any case "Paul Rubin" wrote in message news:7x************@ruckus.brouhaha.com... Nick Craig-Wood writes: > I understand the algorithm quite well but how to code the > multiplication > stage most efficiently in python eludes me. You might want to look at http://gmpy.sourceforge.net/ It has very fast multiplication up to any size you like! I think he's talking about point multiplication on the elliptic curve group, not integer multiplication. Jul 18 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.