Idea for modulo with fixed n in GMP

[Vincent Diepeveen]

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,  
especially
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.

Vincent

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 gmplib.org/devel/ 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
>