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.

Show thread

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

Show thread

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.

Show thread

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.

Show thread

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

Show thread

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

Show thread
Follow

Math communication is difficult and rarely well-done.

Sign in to participate in the conversation
Mathstodon

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