A. Esposito A. Esposito - 1 year ago 54
Javascript Question

Modulo operation on a very large number

How would you go about performing a modulo operation on a fairly large number where modular exponentiation approaches cannot be taken?

For example, take this prime number modulo operation:

91115057151 % 4

WolframAlpha tells me it's 3. That's great, but I'd like to write an algorithm so that my own calculator app can handle that.

I'm assuming that for such a large number I would store the number in an array, one element per digit.

Answer Source

I don't have enough reputation to comment, but these two guys that say, that you can look only at last digits are wrong, take %7 for example - you always have to look at all digits.

As you probably know (a+b)%n = (a%n + b%n) % n and (a*b)%n = (a%n * b%n) % n Using that we can first calculate 1%n, 10%n, 100%n and so on, then multiply these values by digits you have in your number and at the end add it all together.

I wrote it in c++:

//assume we have number of length len in reversed order
//example: 123%9 -> n = 9, num[0] = 3, num[1] = 2; num[2] = 1, len = 3
int mod(int n, int num[], int len)
    int powersOf10modn = 1;
    int anwser = 0;
    for(int i = 0; i < len; i++)
        anwser = (anwser + powersOf10modn * num[i]) % n;
        powersOf10modn = (powersOf10modn*10) % n;
    return anwser;