x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 290

# help to do calculation

i have three vars, all integer

caled m,e and n
i want to do this calculation in c

m^e mod n

do i need a header, or not what is the exact syntax for this, to get the order of computation correct. thanks kieran
0
kplonk
• 7
• 6
• 4
• +3
1 Solution

Commented:
power(int x, int n)
{
int  index;
int  result;

result = 1;
for (index = 0; index < n; index++)
result = result* x;
return(result);
}

/* To calculate m^e mod n */
answer = power(m, e) % n;

This assumes that e is positive.
If you use large numbers you will have to use larger variable types, e.g. long.
0

Commented:
Change the first line to
int power(int x, int n)
0

Commented:
Hi,

Although this introduce several casts, it might be the most clean way to do the calculation, since you use the standard libs:

#include <math.h>

answer = ((int) pow((double) m, (double) e)) % n;
0

Commented:
int pmod(int m,int e,int n){
int p;
if( e == 0 ){ return 1; }
p = pmod(m,e>>1,n);
p *= p;
if( e&1 ){ p *= m; }
return p%n;
}

0

Commented:
ozo, why 'e>>1' and not simply 'e/2' ? speed ?

Arnon David.
0

Commented:
'e>>1' for symmetry with 'e&1', and to raise suspicion about it working with e negative.
('e&1' usually works better than 'e%2' for negative e, but in this case, speed may be the only difference)
0

Author Commented:
E(m)=m^e mod n = c
D(c)=c^d mod n

using e and d =11 and n=35

any value of m should give a value of c and then when c is in the second formual i should get back to m but this dont work, for some reason. is % the mod that i want?
0

Commented:
e and d =11 and n=35 should work.
but if you are using PC_User321's or hernani's method, you are probably overflowing an int.
0

Author Commented:
yer but is this the correct, version of mod i am not sure that this is the thing that i am looking for, eg if m is 3 and e=11 n=35 then encyrapting gives 12 and decrypting gives 3 all is well, but 4 does not work so i recok ythe mod i asm using is not the correct interpretation of mod. what you reckon.
0

Commented:
3^11 % 35 = 12 is correct
12^11 % 35 = 3
4^11 % 35 = 9
9^11 % 35 = 4
But 9^11 = 31381059609, which overflows a 32 bit int,
So you can't use the method proposed by PC_User321 or hernani
0

Commented:
. unless you heed the warning in the last line of PC_User321's post.
0

Commented:
Even a 64 or 128 bit long would not suffice for 34^29
0

Commented:
Let me rephase that:

My method will work fine.  You must heed the warning on the last, which says "If you use large numbers you will have to use larger variable types, e.g. long."

In particular you should ensure that the types used for 'result' and 'power' can hold the size of the result of the exponentiation.

0

Commented:
Let me rephase that:

My method will work fine.  You must heed the warning on the last, which says "If you use large numbers you will have to use larger variable types, e.g. long."

In particular you should ensure that the types used for 'result' and 'power' can hold the size of the result of the exponentiation.

0

Commented:
>> Even a 64 or 128 bit long would not suffice for 34^29

True.
How about a 256 bit long? There might be machines that support it.
People who push the limits must take care.
0

Commented:
or if such a type does not exist, you may prefer a method that only requires a type sufficient to hold the size of the result of the mod.
0

Author Commented:
i will try with long, i reckon this is the prob
0

Commented:
The method I gave you should have no problem with 9^11 mod 35, even if your ints are only 16 bits
0

Commented:
Wouldn't
4^5 % 35 = 9
9^5 % 35 = 4
be more in the spirit of things, considering that 5 x 7 = 35 and
(4 x 6) +1 = 25 whose factors are 5?

And you should stick with ozo's method.
0

Author Commented:
thanks for all the help
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.