How to perform (a * b) % c fast, where a,b,c are ulong, and usually pretty big

Question

All values (a, b, c) are ulongs and can get pretty large (they go up to ulong.Max sometimes as well)

How can I make (a * b) % c execute fast. I have done a whole bunch of research into modular multiplication, but have not been able to find anything useful. So what is a (preferably THE) fastest way to compute this? I know that I can use BigInteger but BigInteger is horribly slow, so I am not going to use it.

Another thing that could work for me is highbits and lowbits % c (because I can use Math.BigMul). But I have not been able to find anything that works for 64 bit for that (only up to 63 bits).

Answer 1

Here is a reasonably fast implementation that uses the Math.BigMul method (.NET 5 and later), and the decimal data type:

/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
    ulong high = Math.BigMul(a, b, out var low);
    if (high == 0) return low % modulo;
    if (high <= 0xFFFFFFFF) return (ulong)(((decimal)a * b) % modulo);
    decimal remainder = high;
    remainder *= 0x100000000;
    remainder += low >> 32;
    remainder %= modulo;
    remainder *= 0x100000000;
    remainder += low & 0xFFFFFFFF;
    remainder %= modulo;
    Debug.Assert((BigInteger)remainder == ((BigInteger)a * b) % modulo); // Validation
    return (ulong)remainder;
}

This implementation performs the operation in two steps, in order to overcome the 96 bit limitation of the decimal type. It's almost 2 times faster than using the BigInteger type, and it doesn't allocate memory. In case the product of the two numbers fits in the decimal range, the result is obtained in one step.

For a similar but slightly slower implementation that doesn't depend on the Math.BigMul method (source code), you can look at the 4th revision of this answer.

---

Update: The (a * b) % c operation could be even faster if you could use a native UInt128 type. Unfortunately this type does not exist. If you are feeling adventurous you could use the Dirichlet .NET Number Theory Library by Rick Sladkey (MIT License), that includes this type (along with the Int128). You could just download the UInt128.cs code file, and include it in your project. Then you could do this:

public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
    return (new Dirichlet.Numerics.UInt128(a) * b) % modulo;
}

It's around 2.5 times faster than the BigInteger in my PC.

This code file has ~2.700 lines of code. if you are interested only in the (a * b) % c functionality, you could probably strip it down to 150 lines or so, if you think it's worth the effort.

Answer 2

Answer found and adapted from https://stackoverflow.com/a/18680280/14133865

public static ulong ModMul(ulong a, ulong b, ulong modulus)
{
    ulong result = 0UL;

    if (b >= modulus)
    {
        if (modulus > 0x7FFFFFFFFFFFFFFF)
        {
            b -= modulus;
        }
        else
        {
            b %= modulus;
        }
    }

    while (a != 0UL)
    {
        if ((a & 1UL) != 0UL)
        {
            if (b >= modulus - result)
            {
                result -= modulus;
            }

            result += b;
        }

        a >>= 1;

        ulong temp = b;

        if (b >= modulus - b)
        {
            temp -= modulus;
        }

        b += temp;
    }

    return result;
}