question on "mult,mod" performance

[Paul Zimmermann]

> 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 <http://www.inria.fr/rrrt/rr-5834.html>, Section 2.1.

Paul Zimmermann