Idea for modulo with fixed n in GMP

Torbjorn Granlund tg at
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 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 mailing list