Fast Modular Multiplication

Modular multiplication is arguably the most computationally-dominant arithmetic primitive in any cryptographic system.

Read the full paper on our Github

Introduction

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.

Full paper at:

[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.

Modular Multiplication on a Circle

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

--

--

Ingonyama means Lion. We are a next-generation semiconductor company, designing accelerators for Zero Knowledge cryptography.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ingonyama

Ingonyama means Lion. We are a next-generation semiconductor company, designing accelerators for Zero Knowledge cryptography.