I'm learning about the Montgomery reduction method for modular multiplication of large integers. I read from several sources. Reading the wikipedia article was not enlightening. Reading a chapter from Handbook of Practical Cryptography was better but still not helpful. The Handbook had tidy psuedocode for it, which I successfully implemented in Rust. I still had no clue how it worked.

The explanations for how the algorithm works were very rigorous and at a high level. So, not very helpful for understanding. I got frustrated with it.

Finally I picked some small numbers and worked through the algorithm with pencil and paper. It worked perfectly and I instantaneously understand the method.

Basically you have a number you want to invert with respect to a large power of two. You represent the number and whatever modulus you are using in binary. Then you add the modulus strategically, shifting it as needed in order to cancel out the 1s in the number you want to invert.

Eventually you will have a much larger number with a lot of trailing zeros in its binary representation, which means it is a multiple of a large power of two.

It is very easy to divide this by a large power of two simply by discarding the trailing zeros.

In the end, I feel like I could have reinvented this method on my own before ever understanding what was written about it.

Math communication is difficult and rarely well-done.

@lopeetall I want that on a t-shirt

@lopeetall I like mine medium-rare :-)

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!