How to calculate modulo?

Question

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 ?

Answer 1

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

Answer 2

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

in the terminal for more information about this function.

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].

Answer 3

If you want to handle numbers:

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

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.

If you need more information check this.

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...

Answer 4

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