question on "mult,mod" performance
tege at swox.com
Mon Apr 17 13:09:45 CEST 2006
Tingjian Ge <tingjian_ge at yahoo.com> 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
There isn't any interfaces for mult-mod in GMP.
More information about the gmp-discuss