Re: Compare modular multiplication algorithms in terms of speed

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 07/31/03 

Date: Thu, 31 Jul 2003 12:22:51 GMT

George Joseph wrote:

> I would like to compare my modular multiplication algorithm to
Montgomery &
> Barrett (I think these algorithms are the fastest in terms of modular
> multiplication, if I'm wrong please tell me).
>
> Would it prove to be worthwhile result if I compare my algorithm to
> Montgomery/Barrett implemented my programming skills, rather than using
> MIRACL or LibTomMath?
>
> For example: (a*b) mod(c) a,b,c = n bits long (excluding all
> precomputations)
> for n=512bits My Montgomery = 50ms per iteration, My method = 35ms per
> iteration and MIRACL Montgomery = 5us per iteration.

I'd say the thing to do is describe the algorithm, and let some
of the crypto-implementors here tear into it.

You'd have to provide a precise description of its workings of
course. Also, try to present at least a proof-sketch showing
that it works (you don't have to make it as rigorous and
unreadable as Peter Montgomery's). Finally say why you think
it's fast.

> Now obviously the programmers who created MIRACL used assembler
coding and
> have done years of optimizations to their code, while I have just
general C
> knowledge. I am not trying to compare who the better programmer is, but
> rather propose an alternative method to Montgomery. Is it worth my while
> trying to optimise my code to MIRACL's standard and then publish it, or
> compare it with my Montgomery & Barrett implementations.

If you can describe it so that it looks likely to faster, I
expect that will generate enough interest to get some optimized
implementations going. 

-- 
--Bryan

Relevant Pages