By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,959 Members | 1,196 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,959 IT Pros & Developers. It's quick & easy.

Elliptic Code

P: n/a
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
Jul 18 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
phr
"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.
Jul 18 '05 #2

P: n/a
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.

Jul 18 '05 #3

P: n/a
Philip Smith <as********@blueyonder.co.uk> wrote:
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!
--
Nick Craig-Wood <ni**@craig-wood.com> -- http://www.craig-wood.com/nick
Jul 18 '05 #4

P: n/a
Nick Craig-Wood <ni**@craig-wood.com> writes:
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!


I think he's talking about point multiplication on the elliptic curve
group, not integer multiplication.
Jul 18 '05 #5

P: n/a
Quite so - but thanks for your help in any case

"Paul Rubin" <http://ph****@NOSPAM.invalid> wrote in message
news:7x************@ruckus.brouhaha.com...
Nick Craig-Wood <ni**@craig-wood.com> writes:
> 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!


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

Jul 18 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.