question on "mult,mod" performance

Paul Zimmermann Paul.Zimmermann at
Mon Apr 17 13:46:37 CEST 2006

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

It depends on the size of your modulus. In the basecase range
(say up to 200 digits) Montgomery's representation is the best one.
See for example what is done in GMP-ECM, file mpmod.c.

For larger size, where subquadratic multiplication comes into play,
you can use either Barrett's reduction or its least-significant-bit
version using Montgomery's representation.

See <>, Section 2.1.

Paul Zimmermann

More information about the gmp-discuss mailing list