2

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 ?

2
  • 1
    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.
    – sinister
    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
1

Lets find pow(x,y)%n

Wikipedia lists this property here.

enter image description 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
2
  • Nice answer! I learned something from this. Jul 26 '14 at 13:43
  • And that's what for Q-A sites are designed.
    – sinister
    Jul 26 '14 at 13:44
1

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

2
  • 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
  • Hi, @ArjunSingh! You're right about this thing! However, you may check this answer for representing large integers in C!
    – kzidane
    Jul 26 '14 at 16:48
0

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

0

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .