Idea for modulo with fixed n in GMP
Vincent Diepeveen
diep at xs4all.nl
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,
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
>
More information about the gmp-discuss
mailing list