make montgomery reduction public?

Torbjorn Granlund tg at
Sun Apr 21 23:15:23 CEST 2013

"William E. Skeith III" <wes_zilla at> writes:

  I was writing to inquire if anyone would support placing redc_1 (and its
  friends) into the public interface.  My particular motivation is that it would
  be helpful in writing specialized exponentiation algorithms, for example those
  that save precomputed values for a fixed base.
  I've written something (straightforward, based on the mpn layer) which works,
  but is about 10% slower than the gmp assembly version for x86_64.[^1]
  I'd be happy to help in the limited ways that I'm capable (perhaps making an
  attempt to draft some documentation?).
We surely will add comprehensive 2-adic reduction code in a not too
distant future.

The functions will probably not be mpn_redc_1 and mpn_redc_2, but
mpn_pi1_bdiv_{q,r,qr} and mpn_pi2_bdiv_{q,r,qr} or something like that.

These functions will allow an m-limb dividend and n-limb divisor, unlike
redc_{1,2} that only handles m = 2n.

I and Niels have been working on this.


More information about the gmp-discuss mailing list