Monthly Archives: April 2022

Optimized Montgomery Multiplication with Smaller Modulus Sizes

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

Posted in Uncategorized | Leave a comment

Montgomery REDC using the positive inverse (mod R)

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

Posted in Uncategorized | 1 Comment

A Faster Multiplicative Inverse (Mod A Power Of 2)

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

Posted in Uncategorized | 1 Comment

Computing the Modular Multiplicative Inverse

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

Posted in Uncategorized | 1 Comment