Modular multiplication without trial division

By P. L. Montgomery. 1985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Private Stateful Information Retrieval (2018, methodology): “In addition, we perform all modular multiplications using the Montgomery representation [40] of multiplicands described in OpenSSL.”
CLKSCREW: Exposing the Perils of Security-Oblivious Energy Management (2017, methodology): “For efficient modular exponentiation, DECRYPTSIG uses the function MONTMULT to perform Montgomery multiplication operations [38,44].”
Handbook of Applied Cryptography (2018, methodology): “32) is due to Montgomery [893], and is one of the most widely used methods in practice for performing modular exponentiation (Algorithm 14.”
Accelerating Fully Homomorphic Encryption over the Integers with Super-size Hardware Multiplier and Modular Reduction (2013, methodology): “Generally, the modular reduction algorithms used in traditional long bit-length cryptography implementations are Montgomery [22] and Barrett reduction [15].”
A Custom Accelerator for Homomorphic Encryption Applications (2017, methodology): “The Montgomery reduction algorithm [41], which is a plausible alternative to the Barrett reduction, can also be used for modular multiplication of 32-bit integers.”
From Euclid's GCD to Montgomery Multiplication to the Great Divide (2001, methodology): “This method is commonly known as the Montgomery multiplication [11].”
A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography (2004, background): “Although relatively efficient algorithms exist for modular reduction (e.g., those of Montogomery [49] or Barrett [50]), selection of a generalized Mersene number forp would also allow modular reduction to be executed as a more efficient sequence of three additions (modp) [51].”
Fault Injection Attacks on Cryptographic Devices: Theory, Practice, and Countermeasures (2012, methodology): “Another speedup in the exponentiation is achieved by employing a multiplication technique known as Montgomery multiplication [22] that greatly simplifies the required modular reductions.”
Accelerating Somewhat Homomorphic Evaluation using FPGAs (2015, methodology): “The Montgomery reduction algorithm [28], which is a plausible alternative to the Barrett reduction, can also be used for modular multiplication of 32-bit integers.”
Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits (2013, methodology): “The underlying modular arithmetic is implemented using Montgomery arithmetic [20], this is contrasted to earlier work which used standard libraries, such as NTL, to provide such operations.”
Exploring the Feasibility of Fully Homomorphic Encryption (2015, methodology): “The most popular algorithms for modular reduction are the Montgomery reduction [20] and the Barrett reduction Fig.”
A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes (2016, methodology): “To use this fast reduction, the ciphertexts have to be handled in base q through the Montgomery [19] representation with respect to m̃ (i.”
Accelerating leveled fully homomorphic encryption using GPU (2014, methodology): “Montgomery reduction [12] and the Barrett reduction algorithms [13] are the most popular modular reduction algorithms.”
A Scalable Dual-Field Elliptic Curve Cryptographic Processor (2003, methodology): “The Montgomery multiplication algorithm [ 18 ], [19] was proposed for modular multiplication in GFOpU to avoid division that requires extensive computations.”
a full RNS implementation of RSA (2004, methodology): “They can be efficiently computed without division using Montgomery’s algorithms [10].”
Accelerating LTV Based Homomorphic Encryption in Reconfigurable Hardware (2015, methodology): “The Montgomery reduction algorithm [28], which is a plausible alternative to the Barrett reduction, can also be used for modular multiplication of 32-bit integers.”