Idea for modulo with fixed n in GMP

Torbjorn Granlund tg at
Sun Apr 20 14:43:58 CEST 2008

Vincent Diepeveen <diep at> 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 mailing list