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 <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > "Philip Smith" <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
