make montgomery reduction public?

William E. Skeith III wes_zilla at
Sun Apr 21 23:02:22 CEST 2013


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?).

Thanks for your consideration.


[1.] The test was for reducing 2048 bit things modulo 1024 bit things via
redc_1, on a sandy bridge.  I manually assembled redc_1.asm and linked it to
my test code -- things might have gone wrong; I'm not sure how influential the
`as` flags are, and I didn't use any of them.

PS: not sure if this is better suited for the gmp-devellist...  apologies if so.    

More information about the gmp-discuss mailing list