A. Esposito - 1 year ago 54

Javascript Question

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:

`6864797660130609714981900799081393217269435300143305409394463459185543183`

3976560521225596406614545549772963113914808580371219879997166438125740282

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