Cryptology ePrint Archive: Report 2019/266

Fast constant-time gcd computation and modular inversion

Daniel J. Bernstein and Bo-Yin Yang

Abstract: This paper introduces streamlined constant-time variants of Euclid's algorithm, both for polynomial inputs and for integer inputs. As concrete applications, this paper saves time in (1) modular inversion for Curve25519, which was previously believed to be handled much more efficiently by Fermat's method, and (2) key generation for the ntruhrss701 and sntrup4591761 lattice-based cryptosystems.

Category / Keywords: implementation / Euclid's algorithm, greatest common divisor, gcd, modular reciprocal, modular inversion, constant-time computations, branchless algorithms, algorithm design, NTRU, Curve25519

Original Publication (with minor differences): IACR-CHES-2019

Date: received 5 Mar 2019, last revised 13 Apr 2019

Contact author: authorcontact-safegcd at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20190413:095943 (All versions of this report)

Short URL: ia.cr/2019/266


[ Cryptology ePrint archive ]