Fast way to manually mod a number

Question

I need to be able to calculate (a^b) % c for very large values of a and b (which individually are pushing limit and which cause overflow errors when you try to calculate a^b). For small enough numbers, using the identity (a^b)%c = (a%c)^b%c works, but if c is too large this doesn't really help. I wrote a loop to do the mod operation manually, one a at a time:

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    {
        long answer = 1;
        for (int x = 0; x < num_exponent; x++)
        {
            answer = (answer * num_base) % mod;
        }
        return answer;
    }

but this takes a very long time. Is there any simple and fast way to do this operation without actually having to take a to the power of b AND without using time-consuming loops? If all else fails, I can make a bool array to represent a huge data type and figure out how to do this with bitwise operators, but there has to be a better way.

Answer 1

Short of writing your own fast modular exponentiation, the simplest idea I can come up with, is to use the F# BigInt type: Microsoft.FSharp.Math.Types.BigInt which supports operations with arbitrarily large scale - including exponentiation and modular arithmetic.

It's a built-in type that will be part of the full .NET framework with the next release. You don't need to use F# to use BitInt - you can make use of it directly in C#.

Answer 2

I'd recommend checking over the Decimal documentation and seeing if it meets your requirements since it is a built in type and can use the mod operator. If not then you're going to need an arbitrary precision library like java's Bignum.

Answer 3

Can you factor a, b, or c? Does C have a known range?

These are 32 bit integers! Go check this site

For instance, here is how you get the mod of n%d where d 1>>s (1,2,4,8,...)

  int n = 137;     // numerator
  int d = 32;      // denom d will be one of: 1, 2, 4, 8, 16, 32, ...
  int m;           // m will be n % d
  m = n & (d - 1);

There is code for n%d where d is 1>>s - 1 (1, 3, 7, 15, 31, ...)

This is only going to really help if c is small though, like you said.

Answer 4

Fast Modular Exponentiation (I think that's what it's called) might work.

Given a, b, c and a^b (mod c):

1. Write b as a sum of powers of 2. (If b=72, this is 2^6 + 2^3 )
2. Do:
    (1) a^2 (mod c) = a*
    (2) (a*)^2 (mod c) = a*
    (3) (a*)^2 (mod c) = a*
    ...
    (n) (a*)^2 (mod c) = a*

3. Using the a* from above, multiply the a* for the powers of 2 you identified. For example:
    b = 72, use a* at 3 and a* at 6.
    a*(3) x a*(6) (mod c)

4. Do the previous step one multiplication at a time and at the end, you'll have a^b % c.

Now, how you're going to do that with data types, I don't know. As long as your datatype can support c^2, i think you'll be fine.

If using strings, just create string versions of add, subtract, and multiply (not too hard). This method should be quick enough doing that. (and you can start step 1 by a mod c so that a is never greater than c).

EDIT: Oh look, a wiki page on Modular Exponentiation.

Answer 5

You could try this:

C#: Doing a modulus (mod) operation on a very large number (> Int64.MaxValue)
http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus-mod-operation-on-a-very-large-number-int64maxvalue/

Answer 6

You can try factoring 'a' into sufficiently small numbers.

If the factors of 'a' are 'x', 'y', and 'z', then

a^b = (x^b)(y^b)(z^b).

Then you can use your identity: (a^b)%c = (a%c)^b%c

Answer 7

It seems to me like there's some kind of relation between power and mod. Power is just repeated multiplication and mod is related to division. We know that multiplication and division are inverses, so through that connection I would assume there's a correlation between power and mod.

For example, take powers of 5:

5 % 4 = 1
25 % 4 = 1
125 % 4 = 1
625 % 4 = 1
...

The pattern is clear that 5 ^ b % 4 = 1 for all values of b.

It's less clear in this situation:

5 % 3 = 2
25 % 3 = 1
125 % 3 = 2
625 % 3 = 1
3125 % 3 = 2
15625 % 3 = 1
78125 % 3 = 2
...

But there's still a pattern.

If you could work out the math behind the patterns, I wouldn't be surprised if you could figure out the value of the mod without doing the actual power.

Answer 8

Python has pow(a,b,c) which returns (a**b)%c (only faster), so there must be some clever way to do this. Maybe they just do the identity you mentioned.

Answer 9

Looks like homework in cryptography.

Hint: check out Fermat's little theorem.

Answer 10

I guess you are looking for : http://en.wikipedia.org/wiki/Montgomery_reduction or the simpler way based on Modular Exponentiation (from wikipedia)

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;

    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }

    return result;
}

Answer 11

Here's an example of Fast Modular Exponentiation (suggested in one of the earlier answers) in java. Shouldn't be too hard to convert that to C#

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html

and the source...

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.java

Answer 12

.NET in general has poor performance for simple math operations. I'd actually look into adding an unmanaged dll into your project.

The GMP library is probably a good candidate as it's fast and has well optimized big integer support... http://gmplib.org/

In fact, I think GMP would support everything you need to do natively, and would be much, much faster than anything you'd write in .NET. I'd just try porting your C# example into an unmanaged C++ project that uses GMP. Then build the C++ project and add it as a reference in your .NET project. You'd end up with a kind of hybrid half managed, half unmanaged application but for heavy math operations like this it can be worth it.