Elliptic Code

[Philip Smith]

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

<phr at localhost.localdomain> wrote in message 
news:m3acqtu6r1.fsf at localhost.localdomain...
> "Philip Smith" <as006d4848 at 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.