Mod operation
Niels Möller
nisse at lysator.liu.se
Wed Nov 25 15:12:37 CET 2009
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
More information about the gmp-devel
mailing list