Idea for modulo with fixed n in GMP
tg at swox.com
Sun Apr 20 14:43:58 CEST 2008
Vincent Diepeveen <diep at xs4all.nl> writes:
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.
I got break even between the new divide-and-conquer code and the "mu"
Barrett code at about 10000 bits, when the total dividend approaches
So for exponent squaring might be idea to take serious look at it.
I am not sure Barrett's algorithm will ever become relevant for
operands in the range one uses for RSA.
With very good short multiplication code, it might be feasible to use
Barrett for such small operands, but I haven't been successful in that
More information about the gmp-discuss