Elliptic Code

[phr 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.