eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
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
-
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}
}
