avoiding adjustments in modular computations

Zimmermann Paul Paul.Zimmermann at loria.fr
Fri Mar 2 17:04:29 CET 2012


I wrote a short note showing that in some cases we can completely avoid
adjustment steps (for example x = x - N) in computations modulo N:


Not only those adjustments might be expensive, for no real mathematical value,
but even if they happen rarely, avoiding the corresponding test might be very
useful, for example if we perform several computations in parallel on a GPU.

This is of course relevant if a future version of GMP provides a layer for
modular arithmetic. But it might also be useful for people on this list.

Any feedback is welcome, including references to related work.

Paul Zimmermann

More information about the gmp-discuss mailing list