Modular multiplication is arguably the most computationally-dominant arithmetic primitive in any cryptographic system.
This note presents an efficient, hardware-friendly algorithm that, to the best of the author’s knowledge, outperforms existing algorithms to date.
The main contribution of this note is to show how Barrett’s Reduction [1], together with good parameter selection and a simple bounding technique, can be used to approximate the quotient l up to a small constant error independent of n, for any n.
Surprisingly, the resulting reduction algorithm closely resembles Montgomery’s Modular-Multiplication algorithm [2], without the coordinate translation requirement. This bounding technique can be used to further lower the calculation complexity of special cases of interest, not presented here, at the price of increased constant error.
Read this paper on our Github: https://github.com/ingonyama-zk/papers/blob/main/modular_multiplication.pdf
[1] Paul Barrett. Implementing the rivest shamir and adleman public key encryption algorithm on a standard digital signal processor. In Advances in Cryptology — CRYPTO’ 86, pages 311–323, 1987.
[2] Peter L. Montgomery. Modular multiplication without trial division. In Mathematics of Computation, volume 44, pages 519–521, 1985.
Follow our Journey
Twitter: https://twitter.com/Ingo_zk
Github: https://github.com/ingonyama-zk
YouTube: https://www.youtube.com/@ingo_zk
Join us: https://www.ingonyama.com/careers
