Monthly Archives: April 2022

This is Part 2 in a planned four part series on Montgomery arithmetic and an application in factoring. Yesterday, Part 1 showed how to use the positive inverse to improve the traditional Montgomery REDC algorithm. If you would like an … Continue reading →

This is Part 1 in a planned four part series on Montgomery arithmetic and an application in factoring. A few days ago, Part 0 (the prequel?) showed how best to calculate the multiplicative inverse. If you would like an excellent … Continue reading →

I’d originally just intended to write up a blog entry on this, but the proofs were a better fit and easier to write in the form of a paper. The paper presents what should generally be the fastest multiplicative inverse … Continue reading →

We’ve previously explored the Extended Euclidean algorithm, and it’s easy to use a special case of it to implement the modular multiplicative inverse. We’ll start by reproducing the final function from an older post that derived a correct and efficient … Continue reading →