question on "mult,mod" performance

Tingjian Ge tingjian_ge at
Mon Apr 17 06:48:44 CEST 2006


My program using GMP performs a large number of
operations each of which is a GMP integer
multiplication followed by a modulo function. 
However, I found that it is slow, and is the
bottleneck of my program.  The modulo operation,
especially, takes most of the time.  It seems that
with GMP, I have to do multiplication and modulo
separately, even though they are one after another. 
I'm wondering if GMP performs any optimization for
this frequent combination (mult followed by mod),
using, say Montgomery algorithm.  From the function
interface, it seems there's only the "powerm" function
that combines power and mod, but not a function that
combines mult and mod.

Am I missing something here?  What's the fastest way
to do a large number of such operations (mult followed
by mod)?


Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 

More information about the gmp-discuss mailing list