Bill Allombert <bill.allomb...@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. -- Torbjörn _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
