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?

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

2 Answers 2

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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