Mod operation

Niels Möller nisse at
Wed Nov 25 15:12:37 CET 2009

Paul Zimmermann <Paul.Zimmermann at> writes:

>> I also wonder if there's some clever way to compute the inverse and m3
>> simultaneously (they're quotient and remainder of B^3 / m). The
>> "obvious" way is newton iteration to get the quotient aka inverse, and
>> anothere multiplication to get the remainder, but maybe they can be
>> combined in the final newton step or something like that.
> you can do this by calling the recursive division with dividend B^3 and
> divisor m. This is exactly half the work done by the recursive division
> for (4n)/(2n), i.e., (3n)/(2n), and will cost 3M(n) in the Karatsuba range.

How does this compare to computing the inverse, floor (B^2 / m_1),
using Newton iteration? I.e., what's the additional cost for also
computing the remainder B^3 mod m?


More information about the gmp-devel mailing list