Fast constant-time gcd and modular inversion

This is the home page for a big ongoing project to optimize constant-time variants of Euclid's algorithm. This is a cross-cutting project with applications to quite a few submissions to NIST's Post-Quantum Cryptography Standardization Project (e.g., optimizing constant-time half-gcd computation inside Goppa/BCH decoding) and to other pre-quantum and post-quantum cryptographic primitives (e.g., optimizing constant-time inversion for Curve25519 and CSIDH).

Contributors, alphabetical order


This work was supported by the U.S. National Science Foundation under grant 1314919, by the Cisco University Research Program, by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005, and by DFG Cluster of Excellence 2092 "CASA: Cyber Security in the Age of Large-Scale Adversaries". This work also was supported by Taiwan Ministry of Science and Technology (MoST) grant MOST105-2221-E-001-014-MY3 and Academia Sinica Investigator Award AS-IA-104-M01. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation" (or other funding agencies).

Version: This is version 2020.11.16 of the "Intro" web page.