Quick way to manually change the number

Question

I need to be able to calculate (a ^ b)% c for very large values ​​of a and b (which individually push the limit and which cause overflow errors when trying to calculate a ^ b). For sufficiently small numbers, the identity (a ^ b)% c = (a% c) ^ b% c is used, but if c is too large, this does not help. I wrote a loop to execute the mod operation manually, one 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 it takes a very long time. Is there an easy and quick way to perform this operation without having to use b without using long cycles? 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 should be a better way.

Answer 1

I think you are looking for: http://en.wikipedia.org/wiki/Montgomery_reduction or an easier way based on modular exposure (from Wikipedia)

 Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) { Bignum result = 1; while (exponent > 0) { if ((exponent & 1) == 1) { // multiply in this bit 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 2

A quick modular exponentiation (I think that what he called) may 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) xa * (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 are going to do this with data types, I do not know. As long as your data type can support c ^ 2, I think everything will be fine.

When using strings, just create string versions of add, subtract and multiply (not too complicated). This method should be fast enough. (and you can start step 1 with mod c so that a never exceeds c).

EDIT: Oh look, the wiki page on Modular Exposure .

Answer 3

Here's an example of fast modular exponentiality (suggested in one of the earlier answers) in java. It shouldn't be too hard to convert this 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 4

Python has pow (a, b, c) that returns (a ** b)% c (only faster), so there must be some smart way to do this. Perhaps they are just making the identity you were talking about.

Answer 5

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

This is a built-in type that will be part of the complete .NET platform with the next version. You do not need to use F # to use BitInt - you can use it directly in C #.

Answer 6

I would recommend checking the Decimal documentation and see if it meets your requirements, as it is a built-in type and can use the mod statement. If not, then you will need a library with arbitrary precision, such as java Bignum.

Answer 7

You can try the following:

C #: Performing a module operation (mod) 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 8

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

If the coefficients "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 9

It seems to me that there is some kind of connection between power and fashion. Power is just re-multiplication, and fashion refers to division. We know that multiplication and division are inverse, so through this connection I would suggest that there is a correlation between the degree and the modulus.

For example, take powers 5:

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

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

In this situation, this is less clear:

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

But there is still a pattern.

If you could work out the math behind the patterns, I would not be surprised if you could understand the meaning of mods without making actual power.

Answer 10

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

These are 32-bit integers! Go check this site

For example, here's how you get mod 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 a code for n% d, where d is 1 → s - 1 (1, 3, 7, 15, 31, ...)

This will only help if c is small, as you said.

Answer 11

It seems like homework in cryptography.

Hint: check Fermat's little theorem .