If you are interested in categories, computation, cryptography, or zero-knowledge proofs, check out my writing for Statebox on zero-knowledge proofs of boolean circuit satisfiability:
Math communication is difficult and rarely well-done.
In the end, I feel like I could have reinvented this method on my own before ever understanding what was written about it.
It is very easy to divide this by a large power of two simply by discarding the trailing zeros.
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.
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.
Finally I picked some small numbers and worked through the algorithm with pencil and paper. It worked perfectly and I instantaneously understand the method.
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.
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.
I took a 768 bit number to a 768 bit exponent on an old laptop and it was no problem. A 256 bit number is enough to enumerate every atom in the observable universe, so just one of these numbers could enumerate the number of atoms in *checks calculator* an imaginary universe in which every atom contains in own universe, and every atom in that universe contained it's own universe, too.
It gives me great appreciation for the Hindu-Arabic numeral system. That huge numbers can be represented in a small space, and that addition, multiplication, and exponentiation can be done digit-by-digit is so crucial to efficient computing. It's really amazing.
By the way, I am trying to make a playlist of the best songs about numbers. Something mathematical must appear in the lyrics to qualify. "Carry the Zero" by Built to Spill counts, as does "One" by Three Dog Night, which literally counts: 1, 2. "One" by U2 does NOT count and therefore does not count. "1234" by Feist technically counts but does not count as a number song since she is counting beats in a musical capacity rather than referring to quantities.
What are your favorite number songs?
Near the end of Built to Spill's "Carry the Zero" I involuntarily stood up as if I were in a charismatic church service.
The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!