Idea for modulo with fixed n in GMP

Vincent Diepeveen diep at
Sun Apr 20 13:34:15 CEST 2008

After some googling i found some paper descriptions of Barrett's.
Indeed it is the same.

I will have a look at the implementation. Note that at > 100k bits,  
million bit range it is more than factor 2 faster than division  
method to take modulo.

So for exponent squaring might be idea to take serious look at it.


On Apr 20, 2008, at 8:00 AM, Torbjorn Granlund wrote:
> If I read your code right, this is the multiply-by-inverse algorithm,
> known as Barrett's algorithm.
> You might want to look at the area, under New
> division code.  The file mpn/generic/mu_div_qr.c implements a
> short-inversion variant of Barrett's algorithm.  The code is just at
> the mpn level now, and we're missing fast (truncating) inversion.
> -- 
> Torbjörn

More information about the gmp-discuss mailing list