Optimized Binary GCD for Modular Inversion
In this short note, we describe a practical optimization of the well-known extended binary GCD algorithm, for the purpose of computing modular inverses. The method is conceptually simple and is applicable to all odd moduli (including nonprime moduli). When implemented for inversion in the eld of integers modulo the prime 2255 − 19, on a recent x86 CPU (Co ee Lake core), we compute the inverse in 6253 cycles, with a fully constant-time implementation. Note. An initial version of this note used a slightly more aggressive algorithm (k iterations of the inner loop instead of k − 1) which was wrong. The gap in the proof was discovered by Tim Taubert, and further discussions showed a counterexample for which the algorithm failed. The current version of the algorithm, and the revised proof, are believed correct. A side e ect of the x is to enable extra optimizations in the implementation of the inner loop, leading to substantially better performance, now at 6253 cycles (from an original 7490 cycles).