Re: Elliptic Code

[Philip Smith]

Quite so - but thanks for your help in any case

"Paul Rubin"  wrote in message 
news:[EMAIL PROTECTED]
> Nick Craig-Wood <[EMAIL PROTECTED]> 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. 


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Elliptic Code

[Paul Rubin]

Nick Craig-Wood <[EMAIL PROTECTED]> 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.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Elliptic Code

[Nick Craig-Wood]

Philip Smith <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> -- http://www.craig-wood.com/nick
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: 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

<[EMAIL PROTECTED]> wrote in message 
news:[EMAIL PROTECTED]
> "Philip Smith" <[EMAIL PROTECTED]> 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. 


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Elliptic Code

[phr]

"Philip Smith" <[EMAIL PROTECTED]> 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.
-- 
http://mail.python.org/mailman/listinfo/python-list

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 


-- 
http://mail.python.org/mailman/listinfo/python-list