[2 days left] Whatâ€™s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
Solved

# help to do calculation

Posted on 2000-03-08
Medium Priority
285 Views
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
Question by:kplonk
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 7
• 6
• 4
• +3

LVL 5

Expert Comment

ID: 2598514
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

LVL 5

Expert Comment

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

Accepted Solution

hernani earned 30 total points
ID: 2598721
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

LVL 84

Expert Comment

ID: 2598985
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

LVL 3

Expert Comment

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

Arnon David.
0

LVL 84

Expert Comment

ID: 2599577
'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 Comment

ID: 2602333
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

LVL 84

Expert Comment

ID: 2603195
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 Comment

ID: 2608371
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

LVL 84

Expert Comment

ID: 2608395
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

LVL 5

Expert Comment

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

LVL 84

Expert Comment

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

LVL 5

Expert Comment

ID: 2608542
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

LVL 5

Expert Comment

ID: 2608549
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

LVL 5

Expert Comment

ID: 2608551
>> 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

LVL 84

Expert Comment

ID: 2608552
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 Comment

ID: 2608564
i will try with long, i reckon this is the prob
0

LVL 84

Expert Comment

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

LVL 3

Expert Comment

ID: 2617467
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 Comment

ID: 2694916
thanks for all the help
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
###### Suggested Courses
Course of the Month13 days, 13 hours left to enroll