# How to calculate modulo?

From the cryptography video short(Week2) , can anybody tell how to compute the value of m = c^d (mod n) ?

How do we find that 658^185(mod 989) equals 67 ?

• Tip : There is a way to calculate x%y without using '%' operator. x%y = x-y*(int(x/y)). Assuming that x and y are in range of integer datatype. Jul 25 '14 at 13:57
• Thanks for the help. I am able to calculate the modulo of smaller no.s by a c program. But when i am trying to calculate larger no.s like 658 and 185 , i am getting wrong answers. Obvious explanation is that 658^185 is a very large no. and not in the range of the int datatype. So , is there anyway i can find 658^185(mod 989) ? Jul 26 '14 at 5:51

Lets find `pow(x,y)%n`

Wikipedia lists this property here.

Now, since we know how to find the modulus of product of 2 big numbers, then we can use this identity in the following way to do it for the exponential functions.

``````   (a*b) % n = (a%n * b%n) % n
=> (a*b*c) % n = (((a*b) % n) * (c % n) ) % n
=> (a*b*c) % n = (((( a%n * b%n ) % n) * (c%n)) % n
=> (a*b*c*d) % n = ... and so on
``````

We have `x=a(=b=c=d=...(y times))`. Then,

``````mod = x % n;
for (int i = 0 ; i < y-1 ; ++i)
{
mod = (mod * (x % n)) % n;
}
//mod contains the desired value
``````
• Nice answer! I learned something from this. Jul 26 '14 at 13:43
• And that's what for Q-A sites are designed. Jul 26 '14 at 13:44

After watching the short on RSA, I guess you didn't mean the XOR bitwise operator by the symbol (^), but rather, you meant exponent.

The `powl()` function (declared in `math.h`) can be useful for that matter. You may run

``````man powl
``````

I will leave the information I gave before about the XOR bitwise operator in case it is helpful.

The bitwise XOR operator compares the bits of two numbers against each other according to the following truth table

``````bit a   bit b   a ^ b (a XOR b)
0       0       0
0       1       1
1       0       1
1       1       0
``````

For the sake of simplicity, I'll demonstrate with smaller number than 658, 185 and 989

For example, the number 5 in binary is 101 and the number 7 is 111.

``````5 ^ 7 = 101 ^ 111

101
111
---
010
``````

so that's equal to 010 (in binary) or 2 (in decimal).

The modulus (aka remainder and mod) operator (i.e., `%`) works as follows:

Given the following expression

``````10 % 3
``````

the mod operator tells the computer to divide 10 by 3, but NOT to give back the result, but rather, the remainder of this division operation.

``````10 / 3 = 3 r 1
``````

so this returns 1.

It's worth mentioning that the remainder of dividing an integer a by an integer b is in [0, b - 1].

• Thanks for the help. I am able to calculate the modulo of smaller no.s by a c program. But when i am trying to calculate larger no.s like 658 and 185 , i am getting wrong answers. Obvious explanation is that 658^185 is a very large no. and not in the range of the int datatype. So , is there anyway i can find 658^185(mod 989) ? Jul 26 '14 at 5:51
– kzidane
Jul 26 '14 at 16:48

If you want to handle numbers:

• 0 <= number <= 65535 (2^16-1) declare your variables as `unsigned int`s
• 0 <= number <= 4294967295 (2^32-1) declare your variables as `unsigned long int`s
• 0 <= number <= 18446744073709551615 (2^64-1) declare your variables as `unsigned long long int`s

The unsigned means that you can only have possitive numbers. If you also want negative use the same without the `unsigned`. But keep in mind that this will half your MAX.

For larger numbers than the above (as 658^185 for example) you can't represent them in C as it is. You have to include a library for this matter. Read this that proposes this GNU library for numbers that are only limited by your hardware. If you don't have to use C you can also try Python that automatically switches to "infinite" precision bignum numbers.

For the modulo operation the above answers are really explanatory...

Hope I helped...

658^185(mod 989) equals 67 ?

examples for illustration below:

``````      a    b      c                 a     c    b
925 = 1 mod(924)       ->     925 % 924 = 1

b       a        c              a      c     b
658 = 67 ^ 5 mod(989)  ->     67 ^ 5 % 989 = 658
``````