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

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 BitInteger 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).

CodePudding user response：

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;
}

CodePudding user response：

If your numbers overflow in the decimal range only rarely, you could use the trivial ModuloMultiplication method below:

/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
    ulong high = Math.BigMul(a, b, out _);
    if (high == 0) return (a * b) % modulo;
    if (high <= 0xFFFFFFFF) return (ulong)(((decimal)a * b) % modulo);
    return (ulong)(((BigInteger)a * b) % modulo);
}

This implementation uses the Math.BigMul method (.NET 5 and later), in order to decide whether a decimal or a BigInteger is required for the operation.

If your numbers overflow in the decimal range almost always, you could use this algorithmic implementation:

/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
    decimal decimalA = a;
    decimal result = decimalA * (b & 0xFFFFFFFF);
    result %= modulo;
    b >>= 32;
    if (b == 0) return (ulong)result;

    decimalA *= 0x100000000;
    decimalA %= modulo;
    result  = decimalA * b;
    result %= modulo;
    return (ulong)result;
}

This implementation performs the operation in two steps, in order to overcome the 96 bit limitation of the decimal type. It's about 50% faster than the BigInteger-based implementation (it performs 50% more calculations in the same amount of time), and it doesn't allocate memory.