Compare modular multiplication algorithms in terms of speed

From: George Joseph (george.joseph_at_student.up.ac.za)
Date: 07/31/03 

Date: Thu, 31 Jul 2003 13:58:08 +0200

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.

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.

Regards
"Clueless" George

Relevant Pages

  • Re: Compare modular multiplication algorithms in terms of speed
    ... > Would it prove to be worthwhile result if I compare my algorithm to ... I'd say the thing to do is describe the algorithm, ... > have done years of optimizations to their code, ... > rather propose an alternative method to Montgomery. ...
    (sci.crypt)
  • Re: Parallel application ran more slowly than the sequential one?
    ... > Could you tell me what are the reasons to make an parallel application ... Your parallel algorithm may be less efficient than your serial algorithm. ... loading/unloading MPI data structures, sharing files over NFS, process ... Compare the runtime of your parallel program to ...
    (comp.parallel)
  • Re: count of each word occurred
    ... > take each word in order and compare it with the rest of the list ... Another version of this algorithm takes advantage of the fact that it does ... loop over all words in the list ... a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Reading and writing a big file in Ada (GNAT) on Windows XP
    ... common cases (no mapping, single character patterns, and so on). ... block move and compare instructions because they fouled up the pipeline and ... So in this case a better algorithm is probably the way to go (and I ... the source length is>M and the pattern length is>N, ...
    (comp.lang.ada)
  • Re: ArrayList BinarySearch vs Contains
    ... whether a required sorting operation will actually reduce the overall ... performance of an algorithm so that it becomes worse than a linear ... A Linear search does a Fast Compare and a fast iteration to the next ...
    (microsoft.public.dotnet.languages.csharp)