Open AccessFast constant-time gcd computation and modular inversion
Author(s) -
Daniel J. Bernstein,
BoYin Yang
Publication year - 2019
Publication title -
iacr transactions on cryptographic hardware and embedded systems
Language(s) - English
Resource type - Journals
ISSN - 2569-2925
DOI - 10.46586/tches.v2019.i3.340-398
Subject(s) - fermat's last theorem , ntru , modular design , cryptosystem , computation , inversion (geology) , constant (computer programming) , computer science , algorithm , time complexity , mathematics , discrete mathematics , cryptography , programming language , paleontology , structural basin , biology
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.