Author Archives: hurchalla
The Montgomery Fused Multiply-Add
This is Part 3 in a planned four part series on Montgomery arithmetic and an application in factoring, starting with Part 1. If you would like an excellent implementation of Montgomery arithmetic and modular arithmetic in general for up to 128 bit … Continue reading
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
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
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
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
[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
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
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
There’s No Such Thing As Certainty
Wouldn’t it be nice to know we’re created completely correct software that has no errors or mistakes whatsoever? How about just one super simple function? In that case, maybe we could do exhaustive testing and try every single possible combination … Continue reading
Google Test Projects in Visual Studio
This is a continuation of the blog entry on a quick start guide to setting up Google Test, this time specific to Visual Studio. First Things First If you used the quick start guide to set up Google Test, you … Continue reading