Solved

help to do calculation

Posted on 2000-03-08
20
279 Views
Last Modified: 2012-03-15
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
Comment
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
  • Learn & ask questions
  • 7
  • 6
  • 4
  • +3
20 Comments
 
LVL 5

Expert Comment

by:PC_User321
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;


No headers are necessary.
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

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

Accepted Solution

by:
hernani earned 10 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 84

Expert Comment

by:ozo
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;
}

answer = pmod(m%n,e,n)
0
 
LVL 3

Expert Comment

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

Arnon David.
0
 
LVL 84

Expert Comment

by:ozo
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)
I'd have made e unsigned, but the question asked for int
0
 

Author Comment

by:kplonk
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

by:ozo
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

by:kplonk
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

by:ozo
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

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

Expert Comment

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

Expert Comment

by:PC_User321
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

by:PC_User321
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

by:PC_User321
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

by:ozo
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

by:kplonk
ID: 2608564
i will try with long, i reckon this is the prob
0
 
LVL 84

Expert Comment

by:ozo
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

by:3rsrichard
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

by:kplonk
ID: 2694916
thanks for all the help
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
C++ vs C compilers 13 164
outlook office 365 8 159
Create a worker thread ( servicing thread) using the Message queue 3 22
keep track of class structure 1 22
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 is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question