Idea for modulo with fixed n in GMP
tg at swox.com
Sun Apr 20 08:00:49 CEST 2008
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.
More information about the gmp-discuss