Cryptology ePrint Archive: Report 2020/972

Optimized Binary GCD for Modular Inversion

Thomas Pornin

Abstract: 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 non-prime moduli). When implemented for inversion in the field of integers modulo the prime $2^{255}-19$, on a recent x86 CPU (Coffee Lake core), we compute the inverse in 6253 cycles, with a fully constant-time implementation.

Category / Keywords: implementation / binary GCD, modular inversion

Date: received 9 Aug 2020, last revised 23 Aug 2020

Contact author: thomas pornin at nccgroup com

Available format(s): PDF | BibTeX Citation

Version: 20200823:182411 (All versions of this report)

Short URL: ia.cr/2020/972


[ Cryptology ePrint archive ]