2-adic Svoboda

Torbjörn Granlund tg at gmplib.org
Mon May 3 07:50:24 UTC 2021

Paul Zimmermann <Paul.Zimmermann at inria.fr> writes:

  I tried to implement Montgomery-Svoboda at the C level, but did not manage
  to beat the mpn_redc_x routines. I'm very interested to see your results!

Without invariance from e.g modexp, I don't believe one can beat
sbpi1_bdiv_r (or the older redc_1).  Newer implementation of
sbpi1_bdiv_r make use of the observation that the next quotient can be
computed early, actually almost a whole innerloop invocation early,
which makes its cost very low.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list