Efficiently computing multiple modular inverses at once
The Endeavour 2026-01-14
Summary:
Suppose you have a large prime number M and you need to find the inverse of several numbers mod M. Montgomery’s trick is a way to combine the computation of the inverses to take less time than computing the inverses individually. Peter Montgomery (1947–2020) came up with this trick in 1985. We will illustrate Montgomery’s trick by […]
The post Efficiently computing multiple modular inverses at once first appeared on John D. Cook.