question on "mult,mod" performance

Torbjorn Granlund tege at
Mon Apr 17 13:09:45 CEST 2006

Tingjian Ge <tingjian_ge at> writes:

  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)?
There isn't any interfaces for mult-mod in GMP.


More information about the gmp-discuss mailing list