Mod operation

[Niels Möller]

Paul Zimmermann <Paul.Zimmermann at loria.fr> 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?

Regards,
/Niels