This is Part 3 in a three part series on Montgomery arithmetic, starting with Part 1. If you would like an excellent implementation of Montgomery arithmetic and modular arithmetic in general for up to 128 bit integer types, please see Clockwork, a high … Continue reading

## Optimized Montgomery Multiplication with Smaller Modulus Sizes

This is Part 2 in a planned three part series on Montgomery arithmetic. Yesterday, Part 1 showed how to use the positive inverse to improve the traditional Montgomery REDC algorithm. If you would like an excellent implementation of Montgomery arithmetic … Continue reading

## Montgomery REDC using the positive inverse (mod R)

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

Posted in Uncategorized | 2 Comments

## 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

## [C/C++] Surprises and Undefined Behavior From Unsigned Integer Promotion

“There are far too many integer types, there are far too lenient rules for mixing them together, and it’s a major bug source, which is why I’m saying stay as simple as you can, use [signed] integers til you really … Continue reading

Posted in Uncategorized | 3 Comments

## Implementing the Extended Euclidean Algorithm with Unsigned Inputs

As the previous post showed, it’s possible to correctly implement the Extended Euclidean Algorithm using one signed integral type for all input parameters, intermediate variables, and output variables. None of the calculations will overflow. The implementation was given as follows: … Continue reading

Posted in Uncategorized | 11 Comments

## Proof of Bounds for the Extended Euclidean Algorithm

Euclid’s method is a classic algorithm for finding the greatest common divisor (gcd) of two integers. Donald Knuth referred to it as “the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present … Continue reading

Posted in Uncategorized | 4 Comments

## Asymptotic Certainty (Good Enough)

This is something of a philosophical note, imagining we have unlimited time to “ensure” that we produce perfectly correct software that fulfills all requirements.  In practice, we work under real world constraints, with evolving requirements and schedules and specifications, and … Continue reading