Extending the mpn interface

Torbjorn Granlund tg at gmplib.org
Mon Feb 18 11:37:50 CET 2013

Bill Allombert <Bill.Allombert at math.u-bordeaux1.fr> writes:

  On Mon, Feb 18, 2013 at 11:06:01AM +0100, Niels Möller wrote:
  > For powm, I think it uses redc (in the flavor redc_n) also for very large
  > (odd) modulo, even if the difference to plain euclidean division is
  > going to be pretty small.
  In my mind redc is a quadratic algorithm. you probably use another variation.
In my mind redc is a recoding of residues allowing for Hensel-norm
division.  This Hensel-norm division does not create a principal residue
in the recoded system, but a right shift (assuming 2-adic norm) gets us
principal residues.

We actually have separate hensel division function (mpn_*bdiv*) and
redc, but that's probably going to change in the next release.

There are two minor differences between our functions, one is that the
bdiv function allow any dividend size, the other is the "rounding mode"
for the quotient.


More information about the gmp-devel mailing list