Author Archives: hurchalla

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 →

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 →

“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 →

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 →

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 →

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 →

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 →