Elliptic Code

[Philip Smith]

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

 

[phr]

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.

 

[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

 

[Nick Craig-Wood]

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!

 

[Paul Rubin]

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.

 

[Philip Smith]

Quite so - but thanks for your help in any case

I think he's talking about point multiplication on the elliptic curve
group, not integer multiplication.