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

<ph*@localhost.localdomain> wrote in message

news:m3************@localhost.localdomain...

"Philip Smith" <as********@blueyonder.co.uk> 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.