Paper 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
binary GCDmodular inversion
Contact author(s)
thomas pornin @ nccgroup com
History
2020-08-23: last of 2 revisions
2020-08-18: received
See all versions
Short URL
https://ia.cr/2020/972
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/972,
      author = {Thomas Pornin},
      title = {Optimized Binary GCD for Modular Inversion},
      howpublished = {Cryptology ePrint Archive, Paper 2020/972},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/972}},
      url = {https://eprint.iacr.org/2020/972}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.