1
$\begingroup$

What is the best known asymptotic/concrete complexity of modular multiplication?

Using Montgomery multiplication, if $M(n)$ is the cost of one integer multiplication of $n$ bits, then the cost is $2M(n)+o(M(n))$ (assuming comparisons and bit-shifts are $o(M(n))$. Is this the best known?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you care about the time needed for calculating the two Montgomery constants? $\endgroup$
    – garfunkel
    Aug 2 at 15:07
  • $\begingroup$ No; I'm thinking about algorithms/circuits that are "precompiled" for a specific modulus $\endgroup$
    – Sam Jaques
    Aug 2 at 15:58

2 Answers 2

Reset to default
2
$\begingroup$

This seems to be the case for generic moduli $n$ and generic exponents. See the preprint of a chapter entitled "Efficient Modular Multiplication" (available here) from the book Computational Cryptography edited by Joppe W. Bos and Martijn Stam and published by Cambridge University Press, 2021.

There are efficiencies of various tweaks discussed in there in terms of parallelization, latency and area.

Improve this answer
$\endgroup$
0
$\begingroup$

McLaughlin's modular multiplication computes $AB/(2^n-1) \bmod N$ in time $O(1.5M(n))$ in the FFT range.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.