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

Posted in Uncategorized | Leave a comment

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

[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

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

Posted in Uncategorized | Leave a comment

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

Posted in Uncategorized | Leave a comment