I have been browsing for the fastest and most efficient modular reduction algorithms and came across quite a few.

But the one in A Fast Modular Reduction Method (2014) by Zhengjun Cao, Ruizhong Wei and Xiaodong Lin is the fastest that I could find. This implementation is based on look-up-table.

Is this the fastest algorithm for performing modular reduction or are there faster methods out there?

  • 2
    $\begingroup$ Please don't forget to vote for cite links - we need them! $\endgroup$ – Maarten Bodewes Feb 26 '16 at 7:22
  • $\begingroup$ Define fastest. At least, define if you want support for arbitrary modulus (needed for at least the private-key computation of RSA, but not all ECC in $\mathbb F_p$), for how many reductions the thing is optimized, and how much memory can be devoted to temporary results. If the definition involves actual implementation on some hardware, define how you make sure the same care was used in implementations compared, the number of registers used, the speed of memory accesses and how the access pattern influences that. $\endgroup$ – fgrieu Feb 26 '16 at 8:00
  • 1
    $\begingroup$ @fgrieu I actually want to use it for ECC. Memory for temporary results is not a problem as long as static allocations at each loop can be minimized. I'm comparing other implementations in my PC (which has a 64 bit processor 4GB RAM and 2GHz). $\endgroup$ – abejoe Feb 26 '16 at 9:06
  • 1
    $\begingroup$ @abejoe: you have not defined if you want support for arbitrary modulus. In the context of ECC over base field $\mathbb F_p$, the fastest modular reduction algorithm depends a lot on the choice of the prime $p$. Often, that choice is made for efficient modular reduction. For example, for the extremely common Curve P-256, $p=2^{256}-2^{224}+2^{192}+2^{96}-1$ and that allows very efficient modular reduction. $\endgroup$ – fgrieu Feb 26 '16 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.